#include "cave.h"
#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;
const int mxN = 5e3+5;
int a[mxN], b[mxN];
int f(int x, int l, int r, int p, int n){
if(l == r){
return l;
}
int mid = l+(r-l)/2;
for(int i=0; i<n; ++i){
a[i] = (i >= l && i <= mid);
}
if(tryCombination(a) != x){
return f(x, l, mid, p, n);
} else {
return f(x, mid+1, r, p, n);
}
}
void exploreCave(int N) {
for(int i=0; i<N; ++i){
a[i] = 0;
b[i] = -1;
}
for(int i=0; i<N; ++i){
int p = a[i];
if(tryCombination(a) == i){
p = a[i] = !a[i];
}
b[i] = f(i, 0, N-1, p, N);
}
answer(a, b);
}
