#include <bits/stdc++.h>
#include "cave.h"
#define MAX 5005
int tryCombination(int S[]);
void answer(int S[], int D[]);
void exploreCave(int N);
bool skip[MAX];
bool padrao[MAX];
int relacao[MAX];
int n;
int tentar(int l=-1,int r=-1){
int combinacao[n];
for(int i=0;i!=n;++i)combinacao[i]=padrao[i];
if(l!=-1){
for(int j=l;j<=r;++j){
if(skip[j])continue;
///Ativar chave
combinacao[j]=1;
}
}
return tryCombination(combinacao);
}
int lessthan(int la,int ra,int obj){
if(la==ra){
return la;
}
int m = (la+ra)/2;
int x = tentar(la,m);
if(x<=obj&&x!=-1){
return lessthan(la,m,obj);
}else return lessthan(m+1,ra,obj);
}
int atleast(int la,int ra,int obj){
if(la==ra){
return la;
}
int m = (la+ra)/2;
int x = tentar(la,m);
if(x>obj||x==-1){
return atleast(la,m,obj);
}else return atleast(m+1,ra,obj);
}
void exploreCave(int N) {
n=N;
for(int i=0;i!=N;++i){
int val = tentar();
int ind=-1;
int esperado=-1;
if(val>i||val==-1){///Tentar botar o valor para i-1 (Garantido que 1 eh a chave primaria)
esperado=0;
ind = lessthan(0,N-1,i);
}else {///Tentar botar o valor para pelo menos i (Garantido que 0 eh a chave primaria)
esperado=1;
ind = atleast(0,N-1,i);
}
skip[ind]=true;
padrao[ind]=esperado;
relacao[ind]=i;
}
int ans1[N],ans2[N];
for(int i=0;i!=N;++i){
ans1[i]=padrao[i];
ans2[i]=relacao[i];
}
answer(ans1,ans2);
}
