제출 #515586

#제출 시각아이디문제언어결과실행 시간메모리
515586kostia244Minerals (JOI19_minerals)C++17
100 / 100
63 ms4428 KiB
#include "minerals.h" #include<bits/stdc++.h> #define all(x) begin(x), end(x) using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); bitset<90000> on; int qcnt = 0; int uwusgi(int x) { on.flip(x); qcnt++; return Query(x); } #define Query uwusgi void _Solve(int N, vector<int> AA, vector<int> B, int pop, int fi) { vector<int> v(1<<pop), V(1<<pop); iota(all(v), 0); for(int i = 0; i < 1<<pop; i++) { V[i] = fi^(i&1); for(int b = 1; b < pop; b++) { V[i] += (i>>b)%2 != (i>>(b-1))%2; } } // shuffle(all(v), rng); stable_sort(all(v), [&](auto x, auto y) { return V[x] < V[y]; }); vector<int> A(1<<pop, -1), C(1<<pop); for(int i = 0; i < N; i++) A[v[i]] = AA[i]; for(int b = 0; b < pop; b++) { int lst = 0, ops = 0, done = 0; for(int i = 0; i < 1<<pop; i++) if(A[i] != -1) ops += ((i>>b)&1)^on[A[i]]; // if(ops > N-ops) // for(int i = 0; i < 1<<pop; i++) if(i < (i^(1<<b))) // swap(A[i], A[i^(1<<b)]); for(int i = 0; i < 1<<pop; i++) if(A[i] != -1) if(((i>>b)&1)^on[A[i]]) lst = Query(A[i]), done++; // cout << ops << " " << N-ops << " " << done << endl; vector<int> cnt(1<<pop), cnto(1<<pop); for(auto i : C) cnt[i]++; for(int i = 0; i < 1<<b; i++) { for(int j = 0; j < 1<<(pop-b); j++) { int c = i | (j<<b); if(A[c]!=-1) cnto[i] += j&1; } } for(int i = 0; i < N; i++) { if(!cnto[C[i]]) {cnt[C[i]]--;continue;} if(cnto[C[i]]) { int qq = -1; if(cnto[C[i]] == cnt[C[i]] && lst != qq) qq = lst;//cout << "HEY"<<endl; else qq = Query(B[i]); if(lst == qq) cnto[C[i]]--; C[i] |= (lst == qq)<<b; lst = qq; } cnt[C[i]]--; } // for(auto i : C) cout << i << " "; cout << endl; } for(int i = 0; i < N; i++) Answer(A[C[i]], B[i]); } void Solve(int N) { vector<int> A, B, X, Y, C(N), V(1<<16); { vector<int> ord(2*N); iota(all(ord), 1); shuffle(all(ord), rng); int lst = 0; vector<int> pref(N), suf(N); for(int I = 0; I < N; I++) { int i = ord[I]; int cc = Query(i); pref[I] = lst != cc; lst = cc; } for(int I = 0; I < N; I++) { int i = ord[I]; int cc = pref[I] ? Query(i) : lst; suf[I] = lst != cc; lst = cc; } for(int i = 0; i < N; i++) { if(suf[i]&&pref[i]) { A.push_back(ord[i]); } else { (pref[i] ? X : Y).push_back(ord[i]); } } for(int I = N; I < 2*N; I++) { int i = ord[I]; int cc = Query(i); (cc == lst ? A : B).push_back(i); lst = cc; } //A - x //B - B } // cout << A.size() << " " << B.size() << endl; // int CC = 0; // cout << A.size() << " " << (1<<15) << endl; // cout << X.size() << " " << (1<<14) << endl; for(auto i : B) assert(on[i]); // cout << qcnt << endl; int lst = qcnt; _Solve(A.size(), A, B, 16, 0); lst = qcnt; _Solve(X.size(), Y, X, 14, 0); // reverse(all(A)); // reverse(all(B)); // for(int i = 0; i < 1<<15; i++) A.pop_back(), B.pop_back(); // _Solve(N-(1<<15), A, B, v); // cout << qcnt << endl; }

컴파일 시 표준 에러 (stderr) 메시지

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:111:6: warning: variable 'lst' set but not used [-Wunused-but-set-variable]
  111 |  int lst = qcnt;
      |      ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...