#include <bits/stdc++.h>
using namespace std;
#include "cave.h"
void exploreCave(int n){
int s[n], d[n];
for(int i = 0; i < n; i++) s[i] = 0, d[i] = 0;
vector<bool> known(n, false);
int cr[n];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++) {
if(!known[j]) s[j] = 0;
else s[j] = cr[j];
}
int calm = tryCombination(s);
if(calm == -1) calm = INT_MAX;
int l = 0, r = n-1;
int res;
while(l < r){
int m = (l+r+1)>>1;
for(int j = m; j <= r; j++){
if(!known[j]) s[j] = !s[j];
else s[j] = cr[j];
}
res = tryCombination(s);
if(res == -1) res = INT_MAX;
if(res != calm){
l = m;
}
else{
r = m-1;
}
calm = res;
}
r = max(r, 0);
d[r] = i;
if(res == i) cr[r] = !s[r];
else cr[r] = s[r];
known[r] = true;
}
answer(cr, d);
}
