#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
const int mxN = 5e3;
bool mark[mxN];
int N;
int Find(int l, int r, int finding, bool open, int S[]) {
if(l == r) {
if(!open) S[l] ^= 1;
return l;
}
int mid = (l + r) >> 1;
for(int i = l; i <= mid; i++) {
if(mark[i]) continue;
S[i] ^= 1;
}
bool open_left;
int x = tryCombination(S);
if(x == -1 || x > finding) open_left = true;
else open_left = false;
if(open ^ open_left) return Find(l, mid, finding, open_left, S);
else return Find(mid + 1, r, finding, open_left, S);
}
void exploreCave(int n) {
int S[n], D[n];
for(int i = 0; i < n; i++) S[i] = 0;
for(int finding = 0; finding < n; finding++) {
bool open;
int x = tryCombination(S);
if(x == -1 || x > finding) open = true;
else open = false;
int fnd = Find(0, n - 1, finding, open, S);
D[fnd] = finding;
mark[fnd] = true;
}
answer(S, D);
}
