#include<bits/stdc++.h>
#include "cave.h"
using namespace std;
const int MAXN = 5010;
void answer(int S[],int D[]);
int tryCombination(int S[]);
bool vis[MAXN];
int aux[MAXN];
int bb(int x,int y,int S[],int k,int p,int n){
int meio = (x + y) / 2;
if(x == y) return x;
for(int i = 0;i < n;i++){
if(i <= meio && vis[i] == false) aux[i] = (S[i] + 1) % 2;
else aux[i] = S[i];
}
int h = tryCombination(aux);
if(h == -1 || h > p) h = 1;
else h = 0;
if(h != k) return bb(x,meio,S,k,p,n);
return bb(meio + 1,y,S,k,p,n);
}
void exploreCave(int n){
int S[MAXN] , D[MAXN];
memset(S,0,sizeof S);
for(int i = 0;i < n;i++){
int h = tryCombination(S);
if(h == -1) h = 10000;
//cout << "/ " << h << endl;
int l;
if(h > i) l = 1;
else l = 0;
//cout << "l " << l << endl;
int t = bb(0,n - 1,S,l,i,n);
D[t] = i;
vis[t] = true;
if(l == 0) S[t] += 1 , S[t] %= 2;
}
answer(S,D);
}
