Submission #815264

#TimeUsernameProblemLanguageResultExecution timeMemory
815264minhcoolAncient Machine 2 (JOI23_ancient2)C++17
0 / 100
30 ms328 KiB
//#define local #ifndef local #include "ancient2.h" #endif #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; //#define int long long #define fi first #define se second #define pb push_back #define mp make_pair typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 3e5 + 5; const int oo = 1e18 + 7, mod = 1e9 + 7; mt19937 rng(1); int rnd(int l, int r){ int temp = rng() % (r - l + 1); return abs(temp) + l; } int n; bitset<1005> basis[1005]; bool vis[1005]; bool ck[1005]; bool ckk(int p, int q){ assert(p > q); int m = 2 * p; vector<int> vc1(m), vc2(m); for(int i = 0; i < m; i++) vc1[i] = i + 1; vc1[2 * p - 1] = p, vc1[p - 1] = 0; vc2 = vc1; vc2[q] += p, vc2[q + p] -= p; //for(auto it : vc1) assert(it >= 0 && it < m); //for(auto it : vc2) assert(it >= 0 && it < m); int temp = Query(m, vc1, vc2); return (temp >= p); } int in(bitset<1005> bts){ bool temp = 0; for(int i = 0; i < 1000; i++){ if(!bts[i]) continue; if(!vis[i]){ vis[i] = 1; ck[i] = temp; basis[i] = bts; return i; } bts ^= basis[i]; temp ^= ck[i]; } return -1; } int cal(bitset<1005> bts){ bool ans = 0; for(int i = 0; i < 1000; i++){ if(!bts[i]) continue; bts ^= basis[i]; ans ^= ck[i]; } return ans; } string s; string Solve(int N){ n = N; s.resize(n); int p = 55; for(int itr = 0; itr < 100; itr++){ vector<int> a(itr + 3), b(itr + 3); for(int i = 0; i < itr; i++) a[i] = b[i] = i + 1; a[itr] = itr + 1; b[itr] = itr + 2; a[itr + 1] = b[itr + 1] = itr + 1; a[itr + 2] = b[itr + 2] = itr + 2; int temp = Query(itr + 3, a, b); if(temp == itr + 1) s[itr] = '0'; else s[itr] = '1'; } for(int itr = 100; itr < 200; itr++){ vector<int> a(101), b(101); for(int i = 0; i < 99; i++) a[i] = b[i] = i + 1; a[99] = b[99] = 0; if(s[itr - 100] == '0') b[itr - 100] = 100; else a[itr - 100] = 100; a[100] = b[100] = 100; int temp = Query(101, a, b); if(temp == 100) s[itr] = char(97 - s[itr - 100]); else s[itr] = s[itr - 100]; } for(int itr = 0; itr < 200; itr++){ bitset<1005> bts; for(int i = 0; i <= 1000; i++) bts[i] = 0; bts[itr] = 1; int pos = in(bts); if(pos < 0) continue; if(s[itr] == '1') ck[itr] ^= 1; } for(int l = 1; l <= 55; l++){ for(int r = 0; r < l; r++){ bitset<1005> bts; for(int i = 0; i <= 1000; i++) bts[i] = 0; for(int i = r; i <= 1000; i += l) bts[i] = 1; int temp = in(bts); if(temp < 0) continue; bool temp2 = ckk(l, r); ck[temp] ^= temp2; } } for(int i = 201; i < 1000; i++){ bitset<1005> bts; bts[i] = 1; s[i] = char(48 + cal(bts)); } return s; } #ifdef local void process(){ } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) process(); } #endif

Compilation message (stderr)

ancient2.cpp:22:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   22 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
ancient2.cpp: In function 'std::string Solve(int)':
ancient2.cpp:82:9: warning: unused variable 'p' [-Wunused-variable]
   82 |     int p = 55;
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...