#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int s[5005], curs[5005], door[5005];
int getstate(int comb, int i){
return (comb > i || comb==-1);
}
void setcurs(int b, int f, int val){
for(int i = b; i < f; ++i){
if(~s[i]) curs[i] = s[i];
else curs[i] = val;
}
}
void exploreCave(int N) {
fill(s, s+N, -1);
for(int i = 0; i < N; ++i){
setcurs(0, N, 0);
int d = 0, state = getstate(tryCombination(curs), i);
for(int j = 12; j >= 0; --j){
setcurs(d, min(d + (1<<j), N), 1);
if(getstate(tryCombination(curs), i) == state) d = min(d + (1<<j), N-1);
else setcurs(d, min(d + (1<<j), N), 0);
}
door[d] = i;
s[d] = (state ? 0 : 1);
}
answer(s, door);
}
