#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
#define MAX 5005
#define sz(x) ((int)x.size())
#define pb push_back
int Q[MAX],S[MAX],state_of_door[MAX];
int N;
int solve(vector<int> &POS,int now,int VAL) {
while(sz(POS)>1) {
int mid=sz(POS)/2-1;
for(int i=0;i<=mid;i++) {
Q[POS[i]]=VAL;
}
for(int i=mid+1;i<sz(POS);i++) {
Q[POS[i]]=!VAL;
}
int cur_door=tryCombination(Q);
if(cur_door==now) {
POS.erase(POS.begin(),POS.begin()+mid+1);
}
else {
POS.erase(POS.begin()+mid+1,POS.end());
}
}
return POS[0];
}
void TRYIT(int now) {
vector<int> POS;
for(int i=0;i<now;i++) {
Q[state_of_door[i]]=S[state_of_door[i]];
}
for(int i=0;i<N;i++) {
if(~S[i]) continue ;
Q[i]=0;
POS.pb(i);
}
int cur_door=tryCombination(Q);
int VAL=(cur_door==now);
int pos_of_now=solve(POS,now,VAL);
state_of_door[now]=pos_of_now;
S[pos_of_now]=VAL;
}
void exploreCave(int N) {
::N=N;
for(int i=0;i<N;i++) S[i]=-1;
for(int i=0;i<N;i++) {
TRYIT(i);
}
int D[MAX];
for(int i=0;i<N;i++) D[state_of_door[i]]=i;
answer(S,D);
}
