#include<bits/stdc++.h>
#include "cave.h"
using namespace std;
bool open(int s[], int i){
int t=tryCombination(s);
if(t==-1||t>i) return 1;
return 0;
}
void exploreCave(int n) {
int s[n]={0},door[n],d[n];
iota(door,door+n,0);
for(int i=0;i<n;++i){
for(int j=i;j<n;++j) s[door[j]]=0;
int low=i,high=n;
bool state=!open(s,i),prev=0;
while(high-low>1){
int mid=(low+high)/2;
//[low,high-1] range in prev state
//[low, mid-1]->state [mid,high]->!state
if(prev==state) for(int k=mid;k<high;++k) s[door[k]]=!state;
else for(int k=low;k<mid;++k) s[door[k]]=state;
if(open(s,i)) {high=mid; prev=state;}
else {low=mid; prev=!state;}
}
swap(door[i],door[low]);
s[door[i]]=state;
}
for(int i=0;i<n;++i) d[door[i]]=i;
answer(s,d);
}
