#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 = 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) ? 1 : 0;
}
bool test_range(int b, int e, int d, vi& used, vi& 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++) {
//cout << i << ' ' << c << endl;
if (used[i])
continue;
if (c >= b && c < e)
t[i] = corr[d];
c++;
}
return tryCombination(t) != 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);
//cout << d << ' ' << corr[d] << endl;
int l = 0;
int h = n - d;
while (l < h - 1) {
int m = (h - l) / 2 + l;
if (test_range(l, m, d, used, pos, corr))
h = m;
else
l = m;
}
int c = 0;
for (int i = 0; i < n; i++) {
if (used[i])
continue;
if (c == l) {
pos[d] = i;
used[i] = 1;
}
c++;
}
}
int S[n];
int D[n];
for (int i = 0; i < n; i++) {
//cout << corr[i] << ' ' << pos[i] << endl;
S[pos[i]] = corr[i];
}
for (int i = 0; i < n; i++)
D[pos[i]] = i;
answer(S, D);
}
