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