#include "cave.h"
#include <bits/stdc++.h>
#define ort (b+s)/2
using namespace std;
const int maxn = 5020;
bool used[maxn];
int ans[maxn], loc[maxn];
int ar[maxn];
void Fill( int b, int e, int t ) {
for(int i=b;i<=e;i++)
if( !used[i] ) ar[i] = t;
}
bool look(int b,int e ) {
for(int i=b;i<=e;i++)
if(!used[i]) return 1;
return 0;
}
int trycom(int ar[]){
int t=tryCombination( ar );
if(t==-1) t=1e9;
return t;
}
int find( int n, int b, int s, int val ) {
if(b==s) return b;
if(!look(b,ort)) return find( n, ort+1, s, val );
if(!look( ort+1,s)) return find( n, b, ort, val );
Fill(b,ort,val);
Fill(ort+1,s,!val);
if(trycom(ar)>n) return find(n,b,ort,val );
return find(n,ort+1,s,val);
}
void exploreCave(int N) {
for(int i=0;i<N;i++) {
Fill(0,N-1,0);
int val=0;
if(trycom(ar)>i)val=0;
else val=1;
int t=find(i,0,N-1,val);
loc[t]=i;
ar[t]=ans[i]=val;
used[t]=1;
}
answer(ar,loc);
}
