#include "minerals.h"
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
bitset<90000> on;
int uwusgi(int x) {
on.flip(x);
return Query(x);
}
#define Query uwusgi
void Solve(int N) {
vector<int> A, B, C(N), V(1<<16);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
{
vector<int> ord(2*N);
iota(all(ord), 1);
shuffle(all(ord), rng);
int lst = 0;
for(auto i : ord) {
int cc = Query(i);
(cc==lst ? B : A).push_back(i);
lst = cc;
}
}
// int CC = 0;
auto AA = A;
A.assign(1<<16, -1);
vector<int> v(1<<16);
iota(all(v), 0);
// for(int b = 0; b < 16; b++) {
// sort(all(v));
// int lst = 0;
// int i = 0;
// while(i < N) {
// int j = i;
// while(j < N && v[j] == v[i]) j++;
// for(int x = 0; i+x < j; x++)
// v[i+x] |= ((x&1)^lst)<<b;//, cout << ((x&1)^lst) << ",";
// int c = 0;
// for(int p = i; p < j; p++) c += (v[p]>>b)&1;
// // cout << lst << " " << c << " " << j-i+1 << endl;
// if((i-j)%2 == 0) lst ^= 1;
// i = j;
// }
// }
for(int i = 0; i < 1<<16; i++) {
V[i] = 1^(i&1);
for(int b = 1; b < 16; b++) {
V[i] += (i>>b)%2 != (i>>(b-1))%2;
}
}
sort(all(v), [&](auto x, auto y) {
return V[x] < V[y] ||
(V[x] == V[y] && x < y);
});
for(int i = 0; i < N; i++)
A[v[i]] = AA[i];
B.resize(1<<16);
for(int b = 0; b < 16; b++) {
int lst = 0, ops = 0, done = 0;
for(int i = 0; i < 1<<16; i++) if(A[i] != -1)
ops += ((i>>b)&1)^on[A[i]];
if(ops > N-ops)
for(int i = 0; i < 1<<16; i++) if(i < (i^(1<<b)))
swap(A[i], A[i^(1<<b)]);
for(int i = 0; i < 1<<16; i++) if(A[i] != -1)
if((((i>>b)&1)^on[A[i]])&&!(A[i^(1<<b)]==-1))
lst = Query(A[i]), done++;
// cout << ops << " " << N-ops << " " << done << endl;
vector<int> cnt(1<<16), cnto(1<<16);
for(auto i : C) cnt[i]++;
for(int i = 0; i < 1<<b; i++) {
for(int j = 0; j < 1<<(16-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]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
1864 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
1916 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
1864 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
1864 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
1864 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
1864 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
1864 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
1864 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
1864 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
