#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int qry(vector <int> S){
int n = S.size(), t[n];
for ( int i = 0; i < n; i++ ) t[i] = S[i];
int x = tryCombination(t);
if ( x == -1 ) x = n;
return x;
}
void ans(vector <int> S, vector <int> D){
int n = S.size(), s[n], d[n];
for ( int i = 0; i < n; i++ ){
s[i] = S[i];
d[i] = D[i];
}
answer(s, d);
}
void exploreCave(int n){
vector <int> p(n), s(n), t;
for ( int i = 0; i < n; i++ ) t.push_back(i);
for ( int i = 0; i < n; i++ ){
int m = t.size();
for ( auto &j: t ) s[j] = 0;
int x = 0;
if ( qry(s) <= i ) x = 1;
int l = 0, r = m - 1;
while ( l < r ){
int md = (l + r) / 2;
for ( int j = 0; j < m; j++ ){
if ( j <= md ) s[t[j]] = x;
else s[t[j]] = x ^ 1;
}
if ( qry(s) <= i ){
l = md + 1;
} else r = md;
}
s[i] = x, p[i] = t[l];
vector <int> nxt;
for ( int j = 0; j < m; j++ ){
if ( j != l ) nxt.push_back(t[j]);
} swap(t, nxt);
}
vector <int> iv(n);
for ( int i = 0; i < n; i++ ){
iv[p[i]] = i;
}
ans(s, iv);
}
