#include "cave.h"
#include <vector>
#include <numeric>
#include <iostream>
using namespace std;
void exploreCave(int n)
{
int s[n], d[n];
vector<int> left(n);
iota(left.begin(), left.end(), 0);
for (int i = 0; i < n; ++i)
{
for (int j : left) s[j] = 0;
int res = tryCombination(s);
if (res == -1) res = n + 1;
if (res >= i + 1)
{
int l = 0, r = (int)left.size() - 1;
while (l != r)
{
int m = (l + r) >> 1;
for (int j = l; j <= r; ++j) s[left[j]] = j > m;
res = tryCombination(s);
if (res == -1) res = n + 1;
if (res >= i + 1) r = m;
else l = m + 1;
}
d[i] = left[l];
left.erase(left.begin() + l);
s[d[i]] = 0;
}
else
{
int l = 0, r = (int)left.size() - 1;
while (l != r)
{
int m = (l + r) >> 1;
for (int j = l; j <= r; ++j) s[left[j]] = j <= m;
res = tryCombination(s);
if (res == -1) res = n + 1;
if (res >= i + 1) r = m;
else l = m + 1;
}
d[i] = left[l];
left.erase(left.begin() + l);
s[d[i]] = 1;
}
}
int nd[n];
for (int j = 0; j < n; ++j) nd[d[j]] = j;
answer(s, nd);
}
