#include "cave.h"
#include <bits/stdc++.h>
#define test tryCombination
using namespace std;
void exploreCave(int N) {
int door[N],ans[N],vis[N];
for(int i=0;i<N;i++){
ans[i]=1;
door[i]=-1;
vis[i]=1;
}
//int curr=test(ans);
// cout<<curr<<endl;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(vis[j]==1)ans[j]=1;
}
int h=test(ans);
int sw=0;
if(h==i){
sw=1;
}
//cout<<"gg=="<<sw<<endl;
for(int j=0;j<N;j++){
if(vis[j]==1)ans[j]=sw;
}
int lo=0,hi=N-1,r;
while(lo<hi){
int mid=(lo+hi)/2;
for(int j=lo;j<=mid;j++){
if(vis[j]==1)ans[j]=sw;
}
for(int j=mid+1;j<=hi;j++){
if(vis[j]==1)ans[j]=(sw^1);
}
r=test(ans);
//cout<<r<<endl;
if(r==i){
hi=mid;
}
else{
lo=mid+1;
}
//cout<<lo<<" "<<hi<<endl;
}
door[lo]=i;
vis[lo]=-1;
ans[lo]=(sw^1);
/*
cout<<lo<<" -< "<<endl;
cout<<"swich"<<endl;
for(int j=0;j<N;j++){
cout<<ans[j]<<" ";
}
cout<<endl;
cout<<"door"<<endl;
for(int j=0;j<N;j++){
cout<<door[j]<<" ";
}
cout<<endl;
cout<<"off"<<endl;
for(int j=0;j<N;j++){
cout<<vis[j]<<" ";
}
cout<<endl;*/
}
answer(ans,door);
}
