#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
//printf("sdffsd %d \n", N);;
int which_switch[N], how_switch[N], used[N], used_ans[N], used_for[N];
memset(which_switch, 0, sizeof(which_switch));
memset(how_switch, 0, sizeof(how_switch));
memset(used, 0, sizeof(used));
memset(used_ans, 0, sizeof(used_ans));
memset(used_for, 0, sizeof(used_for));
//printf("sdffsd %d \n", N);;
for(int i=0;i<N;i++){
//printf("sdffsd %d\n", i);;
vector <int> p, np;
int v[N];
memset(v, 0, sizeof(v));
for(int j=0;j<N;j++){
//printf("%d", used[j]);
if(!used[j])p.push_back(j);
else np.push_back(j);
}
//printf("\n");
int l=0, r=p.size()-1, mid;
for(int j=0;j<np.size();j++)v[np[j]]=used_ans[np[j]];
for(int j=0;j<p.size();j++)v[p[j]]=0;
int res=tryCombination(v);
if(res==i)how_switch[i]=1;
else how_switch[i]=0;
//printf("%d %d\n", i, how_switch[i]);
while(l<r){
mid=(l+r)/2;
for(int j=0;j<np.size();j++)v[np[j]]=used_ans[np[j]];
for(int j=0;j<=mid;j++)v[p[j]]=how_switch[i];
for(int j=mid+1;j<p.size();j++)v[p[j]]=1-how_switch[i];
int res=tryCombination(v);
if(res==i)l=mid+1;
else r=mid;
}
//printf("%d %d\n", l, r);
which_switch[i]=p[l];
used[p[l]]=1;
used_ans[p[l]]=how_switch[i];
used_for[p[l]]=i;
}
answer(used_ans, used_for);
}
