#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
bool biztos0[5000];
bool biztos1[5000];
int ask[5000];
int d[5000];
int s[5000];
int n;
int okk(int a, int b){
for(int i=0;i<n;i++){
if(biztos0[i]){
ask[i]=0;
} else if(biztos1[i]){
ask[i]=1;
} else {
ask[i] = (a<=i && i<=b);
}
}
return tryCombination(ask);
}
int okk2(int a, int b){
for(int i=0;i<n;i++){
if(biztos0[i]){
ask[i]=0;
} else if(biztos1[i]){
ask[i]=1;
} else {
ask[i] = !(a<=i && i<=b);
}
}
return tryCombination(ask);
}
void exploreCave(int N) {
n=N;
for(int i=0;i<n;i++){
int a=0, b=n-1;
bool c=0;
int o = okk(0,n-1);
if(o>i || o==-1){
c=1;
}
while(a!=b){
int k=(a+b)/2;
if(c){
o=okk(a,k);
} else {
o=okk2(a,k);
}
if(o>i || o==-1){
b=k;
} else {
a=k+1;
}
}
//cout << i << ' ' << a << ' ' << c << '\n';
if(c){
biztos1[a]=1;
} else {
biztos0[a]=1;
}
d[a]=i;
s[a]=c;
}
answer(s,d);
}
