#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
const int N = 5010;
int n, S[N], P[N], Q[N];
int test()
{
int x = tryCombination(Q);
if (x == -1) x = n;
return x;
}
void recur(int l, int r, int d, bool ori) // close = 1, open = 0
{
if (l == r) {
P[l] = d;
S[l] = ori ? 1 : 0;
} else {
int m = (l+r)/2;
for (int i = l; i <= m; ++i) {
if (S[i] == -1)
Q[i] = 1;
}
for (int i = m+1; i <= r; ++i) {
if (S[i] == -1)
Q[i] = 0;
}
bool ret = test() <= d;
if (ori == ret) recur(m+1, r, d, ori);
else recur(l, m, d, ori);
}
}
void find_ans(int d)
{
for (int i = 0; i < n; ++i) {
Q[i] = max(0, S[i]);
}
bool ret = test() <= d;
recur(0, n-1, d, ret);
}
void exploreCave(int n)
{
::n = n;
for (int i = 0; i < n; ++i)
P[i] = S[i] = -1;
for (int i = 0; i < n; ++i)
find_ans(i);
answer(S, P);
}
