#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
int n;
void solve(vector<int>v,int bit[],int ans[])
{
if(v.size()==0)
{
answer(bit,ans);
return;
}
int mid=tryCombination(bit);
/*cout<<"mid "<<mid<<endl;
cout<<"start ";
for(int j=0;j<n;j++)
cout<<bit[j]<<' ';
cout<<endl;*/
if(mid==-1)
mid=n;
int mididx;
int curr;
vector<int>right_side;
for(int i : v)
{
bit[i]=1-bit[i];
curr=tryCombination(bit);
if(curr==-1)
curr=n;
/*for(int j=0;j<n;j++)
cout<<bit[j]<<' ';
cout<<endl;
cout<<"ret "<<i<<' '<<curr<<endl;*/
if(curr<mid)
ans[i]=curr;
if(curr>mid)
{
mididx=i;
ans[i]=mid;
}
else if(curr==mid)
right_side.push_back(i);
bit[i]=1-bit[i];
}
bit[mididx]=1-bit[mididx];
/*cout<<endl<<"hello "<<mididx<<endl;
for(int i : right_side)
cout<<i<<' ';
cout<<endl;*/
solve(right_side,bit,ans);
}
void exploreCave(int N)
{
/*cout<<"realS ";
for(int j=0;j<N;j++)
cout<<realS[j]<<' ';
cout<<endl;*/
n=N;
vector<int>v;
for(int i=0;i<N;i++)
v.push_back(i);
int ans[N],bit[N];
for(int i=0;i<N;i++)
{
bit[i]=i%2;
ans[i]=0;
}
solve(v,bit,ans);
}
