結果
問題 | No.2589 Prepare Integers |
ユーザー | Newtech66 |
提出日時 | 2024-08-26 01:45:44 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,220 ms / 2,000 ms |
コード長 | 5,479 bytes |
コンパイル時間 | 3,727 ms |
コンパイル使用メモリ | 205,680 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-08-26 01:45:58 |
合計ジャッジ時間 | 13,154 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 1,220 ms
6,940 KB |
testcase_05 | AC | 797 ms
6,944 KB |
testcase_06 | AC | 533 ms
6,944 KB |
testcase_07 | AC | 447 ms
6,940 KB |
testcase_08 | AC | 215 ms
6,944 KB |
testcase_09 | AC | 107 ms
6,944 KB |
testcase_10 | AC | 144 ms
6,944 KB |
testcase_11 | AC | 173 ms
6,944 KB |
testcase_12 | AC | 619 ms
6,948 KB |
testcase_13 | AC | 506 ms
6,944 KB |
testcase_14 | AC | 424 ms
6,940 KB |
testcase_15 | AC | 427 ms
6,944 KB |
testcase_16 | AC | 354 ms
6,940 KB |
testcase_17 | AC | 225 ms
6,940 KB |
testcase_18 | AC | 180 ms
6,944 KB |
testcase_19 | AC | 177 ms
6,940 KB |
testcase_20 | AC | 109 ms
6,940 KB |
testcase_21 | AC | 132 ms
6,940 KB |
testcase_22 | AC | 147 ms
6,944 KB |
testcase_23 | AC | 170 ms
6,940 KB |
testcase_24 | AC | 192 ms
6,944 KB |
testcase_25 | AC | 191 ms
6,940 KB |
testcase_26 | AC | 184 ms
6,944 KB |
testcase_27 | AC | 71 ms
6,940 KB |
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/istream:39, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/sstream:38, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/complex:45, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ccomplex:39, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/x86_64-pc-linux-gnu/bits/stdc++.h:54, from main.cpp:1: In member function 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long int) [with _CharT = char; _Traits = std::char_traits<char>]', inlined from 'void solve()' at main.cpp:180:19: /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ostream:202:25: warning: 'ans' may be used uninitialized [-Wmaybe-uninitialized] 202 | { return _M_insert(__n); } | ~~~~~~~~~^~~~~ main.cpp: In function 'void solve()': main.cpp:170:44: note: 'ans' was declared here 170 | lol l = 1, r = L.total(), mid, ans; | ^~~
ソースコード
#include<bits/stdc++.h> using namespace std; using lol=long long int; #define endl "\n" const lol mod1=1e9+7,mod2=998244353,mod3=100000000000000003,hashpr=31; const lol inf=9e18+8; const double eps=1e-12; const double PI=acos(-1.0); const int N=1e5+5; #include <ext/pb_ds/assoc_container.hpp> // Common file #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update using namespace __gnu_pbds; using ordered_set_type=lol; typedef tree<ordered_set_type,null_type,less<ordered_set_type>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int exgcd(int a, int b, int& x, int& y) { x = 1, y = 0; int x1 = 0, y1 = 1, a1 = a, b1 = b; while (b1) { int q = a1 / b1; tie(x, x1) = make_tuple(x1, x - q * x1); tie(y, y1) = make_tuple(y1, y - q * y1); tie(a1, b1) = make_tuple(b1, a1 - q * b1); } return a1; } struct LinearBasis{ static const int d = 61; int mod; struct Vector{ int mod; vector<int> vec; Vector(int v, int m):mod(m){ vec.resize(d, 0); vector<int> t; while(v){ t.push_back(v % mod); v /= mod; } for(int i=0;i<(int)t.size();i++){ vec[d-1-i] = t[i]; } } int add(int a, int b){ return a+b>=mod?a+b-mod:a+b; } int sub(int a, int b){ return a>=b?a-b:a-b+mod; } lol to_number(){ lol R = 0; for(int i=0;i<d;i++){ R = mod * R + vec[i]; } return R; } int operator[](int p){return vec[p];} const int operator[](int p) const{return vec[p];} Vector& operator+=(const Vector& other){ for(int i=0;i<d;i++){ if(other[i] == 0) continue; this->vec[i] = add(this->vec[i], other[i]); } return *this; } friend Vector operator+(Vector lhs, const Vector& rhs){ lhs += rhs; return lhs; } Vector& operator-=(const Vector& other){ for(int i=0;i<d;i++){ if(other[i] == 0) continue; this->vec[i] = sub(this->vec[i], other[i]); } return *this; } friend Vector operator-(Vector lhs, const Vector& rhs){ lhs -= rhs; return lhs; } Vector& operator*=(const lol& scalar){ for(int i=0;i<d;i++){ if(this->vec[i] == 0) continue; this->vec[i] = (this->vec[i] * scalar) % mod; } return *this; } friend Vector operator*(Vector lhs, const lol& rhs){ lhs *= rhs; return lhs; } friend Vector operator*(const lol& rhs, Vector lhs){ lhs *= rhs; return lhs; } }; vector<Vector> A; //this is the basis Vector vec(int v){ return Vector(v, mod); } LinearBasis(int m): mod(m){A.resize(d,vec(0));} void add(Vector V){ for(int i=0;i<d;i++){ if(V[i] != 0){ if(A[i][i] == 0){ int s,t; exgcd(V[i], mod, s, t); s = (s % mod + mod) % mod; t = (t % mod + mod) % mod; A[i] = V * s; V = V * (mod / A[i][i]); }else if(V[i] % A[i][i] == 0){ V -= A[i] * (V[i] / A[i][i]); }else{ int s, t; auto W = A[i]; exgcd(V[i], W[i], s, t); s = (s % mod + mod) % mod; t = (t % mod + mod) % mod; A[i] = V * s + W * t; V -= A[i] * (V[i] / A[i][i]); W -= A[i] * (W[i] / A[i][i]); add(W); } } } } lol total(){ lol B = 1; for(int i=0;i<d;i++){ if(A[i][i]) B *= mod / A[i][i]; } return B; } lol kth(lol k){ lol B = total(); if(k > B) return -1; auto R = vec(0); for(int i=0;i<d;i++){ if(!A[i][i]) continue; B /= mod / A[i][i]; int l = min((k - 1) / B, (lol)mod / A[i][i] - 1); int q = (l - R[i] / A[i][i]) % (mod / A[i][i]); if(q < 0) q += mod / A[i][i]; k -= l * B; R += A[i] * q; } return R.to_number(); } }; void solve(){ lol k; int q; cin>>k>>q; auto L = LinearBasis(k); while(q--){ int t; lol x; cin>>t>>x; if(t==1){ L.add(L.vec(x)); }else if(t==2){ cout<<L.kth(x)<<endl; }else{ // You can find the kth smallest number lol l = 1, r = L.total(), mid, ans; while(l<=r){ mid = l + (r - l) / 2; if(L.kth(mid) <= x){ l = mid + 1; ans = mid; }else{ r = mid - 1; } } cout<<ans<<endl; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int _=1; // cin>>_; while(_--) { solve(); } return 0; }