#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int find_pos(int d, vi& pos, vi& corr)
{
int n = pos.size();
vector<int> t(n, 0);
for (int i = 0; i < d; i++)
t[pos[i]] = corr[i];
return tryCombination(t.data()) == d;
}
bool test_range(int b, int e, int d, vi& used, vi& pos, vi& corr)
{
int n = pos.size();
vector<int> t(n, 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.data()) != d;
}
void exploreCave(int n)
{
vi pos(n, -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;
}
vi S(n);
for (int i = 0; i < n; i++)
S[pos[i]] = corr[i];
answer(S.data(), pos.data());
}
