#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int find_pos(int d, int* pos, vi& corr)
{
int n = corr.size();
int t[n];
for (int i = 0; i < n; i++)
t[i] = 0;
for (int i = 0; i < d; i++)
t[pos[i]] = corr[i];
return tryCombination(t) == d;
}
bool test_range(int b, int e, int d, vi& used, int* pos, vi& corr)
{
int n = corr.size();
int t[n];
for (int i = 0; i < n; i++)
t[i] = 1 - corr[d];
for (int i = 0; i < d; i++)
t[pos[i]] = corr[i];
int c = 0;
for (int i = 0; i < n; i++) {
if (used[i])
continue;
if (c >= b && c < e)
t[i] = corr[d];
c++;
}
return tryCombination(t) != d;
}
void exploreCave(int n)
{
int pos[n];
for (int i = 0; i < n; i++)
pos[i] = -1;
vi corr(n, -1);
vi used(n, 0);
for (int d = 0; d < n; d++) {
corr[d] = find_pos(d, pos, corr);
int l = 0;
int h = n - d - 1;
while (l < h - 1) {
int m = (h - l) / 2 + l;
if (test_range(l, m, d, used, pos, corr))
h = m;
else
l = m;
}
pos[d] = l;
}
int S[n];
for (int i = 0; i < n; i++)
S[pos[i]] = corr[i];
answer(S, pos);
}
