#include "cave.h"
#include <bits/stdc++.h>
// solved by bekagg
#define ll long long
#define ent '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define PRaim_bek_abi ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
const int N = 5e5+5;
const int MOD = 1e9+7;
int d[N] , cnt , us[N] , s[N] , p , nn;
void build(int tl , int tr){
for (int i = tl; i <= tr; i++){
s[i] = 1 - s[i];
}
int pos = tryCombination(s);
if (pos == -1) pos = nn;
int tm = (tl + tr) / 2;
if (pos >= p){
return;
}
else {
for (int i = tl; i <= tr; i++){
s[i] = 1 - s[i];
}
if (tl == tr) return;
}
}
void exploreCave(int n){
bool t1 = 1;
for (int i = 0; i < n; i++){
d[i] = i;
s[i] = 0;
int p1 = tryCombination(s) , p2;
s[i] = 1;
p2 = tryCombination(s);
if (p1 == -1){
s[i] = 0;
break;
}
else if (p2 == -1){
s[i] = 1;
break;
}
if (p1 <= i or p2 <= i) {
t1 = 0;
break;
}
if (p1 > i) s[i] = 0;
else s[i] = 1;
}
if (t1 and tryCombination(s) == -1){
answer(s , d);
return;
}
for (int i = 0; i < n; i++) s[i] = 0;
nn = n;
while(cnt < n){
p = tryCombination(s);
if (p == -1) p = n;
if (p == n) break;
build(0 , n - 1);
}
for (int i = 0; i < n; i++){
s[i] = 1 - s[i];
int pos = tryCombination(s);
d[i] = pos;
s[i] = 1 - s[i];
}
answer(s , d);
}
