#include"cave.h"
#include<bits/stdc++.h>
using namespace std;
int tryCombination(int S[]);
void exploreCave(int N)
{
int pos[N],A[N],ans[N];
bool ck[N];
for(int i=0;i<N;i++) ck[i]=true,pos[i]=0;
int pf=tryCombination(pos);
if(pf==-1) pf=N+1;
for(int i=0;i<N;i++)
{
int l=0,r=N-1,p=-1,pp,g,f;
while(p<N-1) p++,pos[p]^=ck[p];
f=tryCombination(pos);
if(f==-1) f=N+1;
bool e=(pf<f);
while(l<=r)
{
int mid=(l+r)/2;
while(p<mid) p++,pos[p]^=ck[p];
while(p>mid) pos[p]^=ck[p],p--;
int res=tryCombination(pos);
if(res==-1) res=N+1;
if(e)
{
if(res!=pf) r=mid-1,pp=mid,g=res;
else l=mid+1;
}
else
{
if(res==f) r=mid-1,pp=mid,g=pf;
else l=mid+1;
}
}
while(p<pp) p++,pos[p]^=ck[p];
while(p>pp) pos[p]^=ck[p],p--;
if(e);
else while(p>=0) pos[p]^=ck[p],p--;
A[pp]=i,pf=g,ck[pp]=false;
}
answer(pos,A);
}
