#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){
if (n > 2000){
int pp = tryCombination(s);
if (pp == -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);
return;
}
for (int i = 0; i < n; i++){
s[i] = 0;
int p1 = tryCombination(s);
s[i] = 1;
int p2 = tryCombination(s);
if (p1 == 0) s[i] = 0;
else if (p2 == 0) s[i] = 1;
}
for (int i = 0; i < n; i++){
s[i] = 1 - s[i];
d[i] = i;
int pos = tryCombination(s);
if (pos == -1) pos = n;
if (pos == i + 1) continue;
s[i + 1] = 1 - s[i + 1];
pos = tryCombination(s);
}
answer(s , d);
return;
}
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);
}
