#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], used[n];
for ( int i = 0; i < n; i++ )
ans[i] = p[i] = used[i] = 0;
for ( int i = 0; i < n; i++ ){
vector <int> a;
for ( int j = 0; j < n; j++ ){
if ( !used[j]){
a.pb(j);
}
}
int m = (int)a.size(), l = 0, r = m - 1;
int a_l = tryCombination(ans);
bool flag = false;
while ( l <= r ){
int md = (l + r) >> 1;
for ( int i = l; i <= md; i++ ) ans[a[i]] = 1;
int a_r = tryCombination(ans);
for ( int i = l; i <= md; i++ ) ans[a[i]] = 0;
if ( min(a_l, a_r) >= i + 1 ) l = md + 1;
else{
if ( l == md ){
flag = a_l < a_r;
break;
}
else r = md;
}
}
l = a[l];
ans[l] = flag;
p[l] = i;
used[l] = true;
}
answer(ans, p);
}
