#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
using ll = long long;
const int mxN = 5e3+10;
bool vis[mxN];
bool check(int l, int r, int elem, int n, int arr[], int i) {
for(int j = l; j <= r; j++) {
if(vis[j]) continue;
arr[j] = 1-elem;
}
int k = tryCombination(arr);
for(int j = l; j <= r; j++) {
if(vis[j]) continue;
arr[j] = elem;
}
return ((k == -1) || (k > i));
}
void exploreCave(int n) {
int ans[n], d[n];
for(int i = 0; i < n; i++) {
int elem;
int curr[n];
memset(curr, 0, sizeof curr);
for(int j = 0; j < n; j++) {
if(vis[j]) curr[j] = ans[j];
}
int k = tryCombination(curr);
if(k > i || k == -1) elem = 1;
else elem = 0;
for(int j = 0; j < n; j++) {
if(vis[j]) curr[j] = ans[j];
else curr[j] = elem;
}
int l = 0, r = n-1;
while(l < r) {
int mid = (l+r+1)/2;
if(check(mid, r, elem, n, curr, i)) {
l = mid;
}
else r = mid-1;
}
d[l] = i;
ans[l] = (1-elem);
vis[l] = true;
}
answer(ans, d);
}
