#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a; i<b; i++)
void exploreCave(int N){
int N1=2*1e6+5;
int fix[N],ans[N],s[N],ans2[N];
rep(i,0,N){fix[i]=-1;ans[i]=-1;}
// ans[j] --> j chamrtvelistvis romeli karia
// fix[i] i karistvis 1 ia tu -1
for(int i=0; i<N; i++){
rep(j,0,N){
if(ans[j]!=-1){
s[j]=fix[ans[j]];
}
else{
s[j]=0;
}
}
int last=tryCombination(s);
if( last<=i and last!=-1){
fix[i]=1;
}
else{
fix[i]=0;
}
int l=0;
int r=N-1;
while(l<=r){
if(l==r){
ans[l]=i;
break;
}
int mid=(l+r)/2;
rep(j,0,l){
if(ans[j]!=-1){
s[j]=fix[ans[j]];
}
else{
s[j]=(fix[i]^1);
}
}
rep(j,l,mid+1){
if(ans[j]!=-1){
s[j]=fix[ans[j]];
}
else{
s[j]=fix[i];
}
}
rep(j,mid+1,N){
if(ans[j]!=-1){
s[j]=fix[ans[j]];
}
else{
s[j]=(fix[i]^1);
}
}
int last=tryCombination(s);
if(last<=i and last!=-1){
l=mid+1;
}
else{
r=mid;
}
}
}
rep(i,0,N){
ans2[i]=fix[ans[i]];
}
answer(ans2,ans);
// ans2 ans
}
