#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int n;
int s[5010], d[5010], tmp;
bool al[5010];
void findElement(int idx){
int ret = 0;
for(int i = 0; i < n; i++){
if(!al[i]) s[i] = 1;
}
ret = tryCombination(s);
if(ret == idx) tmp = 1;
else tmp = 0;
//Real answer should be 1 - tmp
int l, r, mid;
l = 0, r = n - 1;
while(l < r){
mid = (l + r) >> 1;
for(int i = l; i <= mid; i++) if(!al[i]) s[i] = tmp;
for(int i = mid + 1; i <= r; i++) if(!al[i]) s[i] = 1 - tmp;
ret = tryCombination(s);
if(ret == idx) r = mid;
else l = mid + 1;
}
d[l] = idx;
s[l] = 1 - tmp;
al[l] = 1;
}
void exploreCave(int N) {
n = N;
for(int i = 0; i < n; i++){
findElement(i);
}
answer(s, d);
}
//g++ -Wall -lm -static -DEVAL -o cave -O2 -DEVAL grader.c cave.cpp -std=c++14
