#include "cave.h"
#include<bits/stdc++.h>
int n;
int*right,*rightsw,*loc;
int*tryarr;
int tryall(){
for(int i=0;i<n;i++){
if(rightsw[i])tryarr[i]=1;
else tryarr[i]=0;
}
return tryCombination(tryarr);
}
int dd;
int tryrange(int l,int r){
int cnt=0;
for(int i=0;i<n;i++){
if(rightsw[i]!=-1){
tryarr[i]=rightsw[i];
}else{
if(l<=cnt&&cnt<=r)tryarr[i]=right[dd];
else tryarr[i]=!right[dd];
cnt++;
}
}
return tryCombination(tryarr);
}
int getme(int p){
int cnt=0;
for(int i=0;i<n;i++){
if(rightsw[i]==-1){
if(cnt==p)return i;
cnt++;
}
}
//std::cerr<<cnt<<" "<<p<<"\n";
assert(0 && "nuh uh");
return -1;
}
int trylr;
void open(int door){
dd=door;
if(right[door]==-1){
int k=tryall();
if(k==door){
right[door]=0;
}else{
if(k==-1)k=n;
for(int i=door;i<k;i++){
right[i]=1;
}
if(k!=n){
right[k]=0;
}
}
}
int left=n-door;
int l=0,r=left-1,ans=r;
while(l<=r){
int mid=(l+r)>>1;
int val=tryrange(l,mid);
if(val==door){
l=mid+1;
}else{
ans=mid;
r=mid-1;
}
}
//std::cerr<<getme(ans)<<" "<<door<<"\n";
int sw=getme(ans);
loc[sw]=door;
rightsw[sw]=right[door];
}
void exploreCave(int N) {
n=N;
right=new int[N],loc=new int[N],tryarr=new int[N],rightsw=new int[N];
for(int i=0;i<N;i++){
right[i]=rightsw[i]=loc[i]=-1;
}
for(int i=0;i<N;i++){
open(i);
}
answer(rightsw,loc);
}
