#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;
}
Compilation message
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 time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
2140 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
2192 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
2140 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
2140 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
2140 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
2140 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
2140 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
2140 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
2140 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
