#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int n;
int A[5005], D[5005], dd[5005];
int p[5005];
void solve(int idx) {
int T[n];
for (int i = 0; i < idx; i++) T[D[i]] = A[i];
for (int i = 0; i < n; i++) if (!dd[i]) T[i] = 0;
int p = tryCombination(T);
if (p == -1) p = n;
if (idx < p) A[idx] = 0;
else A[idx] = 1;
int l = 0, r = n-1;
while (l != r) {
int mid = (l + r) >> 1;
for (int i = 0; i < n; i++) if (!dd[i]) T[i] = 1-A[idx];
for (int i = l; i <= mid; i++) if (!dd[i]) T[i] = A[idx];
int p = tryCombination(T);
if (p == -1) p = n;
if (idx < p) r = mid;
else l = mid+1;
}
D[idx] = r;
dd[r] = 1;
}
void exploreCave(int N) {
n = N;
fill(A, A + n, -1);
for (int i = 0; i < n; i++) solve(i);
for (int i = 0; i < n; i++) p[i] = i;
int H[N], L[N];
for (int i = 0; i < N; i++) L[D[i]] = i;
for (int i = 0; i < N; i++) H[i] = A[L[i]];
answer(H, L);
}
