#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
const int MAXN = 5010;
int s[MAXN], d[MAXN], aux[MAXN];
void exploreCave(int n){
memset(d, -1, sizeof d);
int x = tryCombination(s);
if(x == -1) x = n;
for(int p = 0;p < n;p++){
int bg = 0, nd = n - 1;
while(bg < nd){
int mid = (bg + nd) >> 1;
for(int i = bg;i <= mid;i++)
if(d[i] == -1)
aux[i] = (aux[i] + 1) % 2;
int y = tryCombination(aux);
if(y == -1) y = n;
if((x > p && y == p) || (x == p && y > p))
x = y, nd = mid;
else
x = y, bg = mid + 1;
}
d[bg] = p;
int z = tryCombination(aux);
s[bg] = (z == p ? (aux[bg] + 1) % 2 : aux[bg]);
aux[bg] = s[bg];
}
answer(s, d);
}
