#include "cave.h"
#include<bits/stdc++.h>
#define lc id<<1
#define rc id<<1^1
const int inf = 1e9;
using namespace std;
int seg[5008 << 2], ans[5008], match[5008];
int cur, depth, ask[5008];
void calc(int id, int l, int r){
seg[id]++;
if (l == r){
match[l] = cur;
if (depth == cur)
ans[l] = (ask[l] ^= 1);
else
ans[l] = ask[l];
return;
}
int mid = (l + r) >> 1;
if (seg[lc] == mid - l + 1){
calc(rc, mid + 1, r);
return;
}
if (seg[rc] == r - mid){
calc(lc, l, mid);
return;
}
int prev = depth;
for (int i = l; i <= mid; i++)
if (ans[i] == -1)
ask[i] ^= 1;
depth = tryCombination(ask);
if (depth == -1)
depth = inf;
if ((prev == cur && depth == cur) || (prev > cur && depth > cur))
calc(rc, mid + 1, r);
else
calc(lc, l, mid);
}
void exploreCave(int N) {
memset(ans, -1, sizeof(ans));
memset(match, -1, sizeof(match));
fill(ask, ask + N, 0);
for (cur = 0; cur < N; cur++){
depth = tryCombination(ask);
if (depth == -1)
depth = inf;
calc(1, 0, N - 1);
}
answer(ans, match);
}
