#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
const int N = 5050;
int n;
int s[N];
int d[N];
mt19937 rnd;
bitset<N> can, an;
int query() {
int t = tryCombination(s);
return t == -1 ? n : t;
}
void exploreCave(int nn) {
n = nn;
fill_n(d, N, -1);
for (int i = 0; i < n; ++i) {
vector<int> f;
can.reset();
for (int j = 0; j < n; ++j) {
if (d[j] == -1) {
f.push_back(j);
can.set(j);
}
}
int q = query();
while (can.count() > 1) {
// cout << can.size() << endl;
vector<int> vec;
an.reset();
for (int e : f) {
if (rnd() % 2) {
vec.push_back(e);
an.set(e);
s[e] ^= 1;
}
}
int t = query();
for (int e : vec) {
s[e] ^= 1;
}
assert(q >= i && t >= i);
if ((q == i) == (t == i)) {
continue;
}
can &= an;
}
int c0 = (int)can._Find_first();
d[c0] = i;
assert(q >= i);
if (q == i) {
s[c0] ^= 1;
}
assert(query() > i);
}
answer(s, d);
}
#ifdef LC
#include "graderlib.c"
int main() {
N = init();
exploreCave(N);
printf("INCORRECT\nYour solution did not call answer().\n");
return 0;
}
#endif
