#include "cave.h"
#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;
const int mxN = 5e3+5;
int a[mxN], b[mxN];
bool done[mxN];
int search(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){
if(done[i]){
continue;
}
a[i] = (i >= l && i <= mid ? p : !p);
}
if(tryCombination(a) != x){
return search(x, mid+1, r, p, n);
} else {
return search(x, l, mid, p, n);
}
}
void exploreCave(int N) {
for(int i=0; i<N; ++i){
a[i] = done[i] = 0;
b[i] = -1;
}
for(int i=0; i<N; ++i){
int p = 0;
for(int j=0; j<N; ++j){
if(done[j]){
continue;
}
a[j] = p;
}
if(tryCombination(a) == i){
p = !p;
}
b[i] = search(i, 0, N-1, p, N);
done[b[i]] = 1;
}
answer(a, b);
}
