#include "cave.h"
int p[10000]={0},a[10000],up[10000];
void dfs(int l,int r,int L,int R,int id){
for(int i=L;i<=R;i++){
if(p[i]!=0) continue;
a[i]+=1;
a[i]%=2;
}
int k=tryCombination(a);
if(L==R && k!=id){
p[L+1]=id;
up[L+1]=a[L+1];
return;
}
if(L==R && k==id){
p[L]=id;
up[L]=a[L];
return;
}
if(k==id){
dfs(L,R,L,(L+R)/2,id);
}
else dfs(R+1,l,R+1,(R+1+l)/2,id);
}
void bfs(int l,int r,int L,int R,int id){
for(int i=L;i<=R;i++){
if(p[i]!=0) continue;
a[i]+=1;
a[i]%=2;
}
int k=tryCombination(a);
if(L==R && k==id){
p[L+1]=id;
up[L+1]=a[L+1];
return;
}
if(L==R && k!=id){
p[L]=id;
up[L]=a[L];
return;
}
if(k!=id){
bfs(L,R,L,(L+R)/2,id);
}
else bfs(R+1,l,R+1,(R+1+l)/2,id);
}
void exploreCave(int n) {
for(int i=0;i<n;i++){
a[i]=1;
}
for(int i=1;i<=n;i++){
int k=tryCombination(a);
if(k!=i){
dfs(0,n-1,0,(n-1)/2,i);
}
else bfs(0,n-1,0,(n-1)/2,i);
}
answer(up,p);
}
