#include<bits/stdc++.h>
#include "cave.h"
using namespace std;
const int MAXN = 5000;
int N;
int S[MAXN], temp [MAXN];
int D[MAXN];
bool done[MAXN];
int test(int l, int r){
for(int i = 0; i < N; i++) temp[i] = S[i];
for(int i = l; i <= r; i++){
if(!done[i]) {
temp[i] = 1;
}
}
return tryCombination(temp);
}
void exploreCave(int _N) {
N = _N;
for(int i = 0; i < N; i++) S[i] = 0;
for(int i = 0; i < N; i++){
// cout << "finding" << " " << i << endl;
int l = 0, r = N - 1;
int val = tryCombination(S);
// cout << val << endl;
while(l < r){
int m = (l + r) / 2;
// cout << l << " " << r << endl;
int t = test(l, m);
if((val == i ? t != i : t == i)){
r = m;
}else{
l = m + 1;
}
}
if(val == i) S[l] = 1;
else S[l] = 0;
D[l] = i;
done[l] = 1;
// cout << l << " " << S[l] << endl;
// cout << l << " " << i << endl;
}
answer(S, D);
}
