#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
const int maxN = 5007;
int n, s[maxN], d[maxN], vis[maxN];
//tryCombination(s[])
//answer(s[], d[])
bool Chk(int mid, int i)
{
for(int i = 0; i < n; ++i) {
if(!vis[i]) {
if(mid) --mid, s[i] = 1;
else s[i] = 0;
}
}
int door = tryCombination(s);
return door == -1 || door > i;
}
void exploreCave(int sz)
{
n = sz;
fill_n(s, n + 1, 0);
fill_n(vis, n + 1, 0);
for(int i = 0; i < n; ++i) {
int cur = tryCombination(s);
bool open = 0;
if(cur == -1 || cur > i) open = 1;
int low = 1, high = n - i;
while(low <= high) {
int mid = (low + high) / 2;
if(Chk(mid, i) != open) high = mid - 1;
else low = mid + 1;
}
(open? s[i] = 0: s[i] = 1);
for(int j = 0; j < n; ++j) {
if(!vis[j]) --low;
if(!low) {d[i] = j, vis[j] = 1; break;}
}
}
answer(s, d);
}
