#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 5000 + 10;
int *S, n, *comb, pans, *D;
inline int get() {
return tryCombination(comb);
}
inline void flip(int l, int r) {
for (int i = l; i <= r; i++)
if (!D[i])
comb[i] ^= 1;
}
void solve(int ind, int l, int r) {
if (l == r) {
D[l] = ind;
if (pans == ind)
comb[l] ^= 1;
S[l] = comb[l];
return;
}
int mid = (l + r) >> 1;
flip(l, mid);
int x = get();
flip(l, mid);
if ((pans == ind) == (x == ind)) solve(ind, mid + 1, r);
else solve(ind, l, mid);
}
void exploreCave(int N_) {
n = N_;
D = new int[n];
S = new int[n];
comb = new int[n];
for (int i = 0; i < n; i++)
D[i] = S[i] = comb[i] = 0;
for (int i = 0; i < n; i++) {
pans = get();
solve(i, 0, n - 1);
}
answer(S, D);
}
// TODO: remove extra one
