#include "cave.h"
#include <bits/stdc++.h>
#define ll long long
#define el cout << '\n'
using namespace std;
int n, *S, *P, *S_copy;
vector<int> A;
bool is_open(int i, int m)
{
int nearest;
if (m == -1)
nearest = tryCombination(S);
else
{
for (int i = 0; i < n; i++)
S_copy[i] = S[i];
for (int j = i; j < n; j++)
S_copy[A[j]] = j <= m;
nearest = tryCombination(S_copy);
}
// cout << "CHECK: " << i << ' ' << m << ' ' << nearest << endl;
return nearest == -1 ? 1 : (nearest > i);
}
void exploreCave(int N)
{
n = N;
A.assign(n, 0);
iota(A.begin(), A.end(), 0);
S = new int[n];
S_copy = new int[n];
P = new int[n];
for (int i = 0; i < n; i++)
S[i] = 0;
for (int i = 0; i < N - 1; i++)
{
bool flag = is_open(i, -1);
int l = i, r = N - 1;
// cout << "START: " << i << ' ' << flag << endl;
while (l < r)
{
int m = l + r >> 1;
if (is_open(i, m) ^ flag)
{
// cout << i << ' ' << m << ' ' << flag << " OK" << endl;
r = m;
}
else
l = m + 1;
}
// cout << "! " << i << ' ' << l << endl;
swap(A[i], A[l]);
S[A[i]] = !flag;
// for (int i = 0; i < N; i++)
// cout << A[i] << ' ';
// cout << endl;
}
for (int i = 0; i < n; i++)
P[A[i]] = i;
answer(S, P);
}
