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