#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
using i64 = long long;
template <typename _F, typename _S>
bool chmax(_F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v;
flag = true;
}
return flag;
}
template <typename _F, typename _S>
bool chmin(_F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v;
flag = true;
}
return flag;
}
void exploreCave(int n) {
int ans[n], p[n];
memset(ans, -1, sizeof(ans));
for ( int i = 0; i < n; i++ ){
vector <int> a;
for ( int j = 0; j < n; j++ ){
if ( ans[j] == -1 ){
a.pb(j);
}
}
int m = (int)a.size(), l = 0, r = m - 1;
bool flag = false;
while ( l < r ){
int md = (l + r) >> 1;
auto L = ans, R = ans;
for ( int i = l; i <= md; i++ ) L[a[i]] = 0;
for ( int i = l; i <= md; i++ ) R[a[i]] = 1;
for ( int i = 0; i < n; i++ ){
chmax(L[i], 0);
chmax(R[i], 0);
}
int a_l = tryCombination(L), a_r = tryCombination(R);
if ( a_l == a_r ) l = md + 1;
else{
if ( l == md ){
flag = a_l < a_r;
}
r = md;
}
}
p[l] = i;
ans[i] = flag;
}
answer(ans, p);
}
