#include "cave.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;
const int MAXN = 5e4+10;
int n;
int a[MAXN], con[MAXN], ty[MAXN];
bool skip[MAXN];
bool coba(int idx){
if(tryCombination(a) == idx) return 1;
return 0;
}
void bin(int idx){
if(!coba(idx)){ //blm ada
for(int i=0; i<n; i++){
if(skip[i]) continue;
a[i] = 1-a[i];
}
}
int l=0, r=n-1, mid=0;
while(l<r){
mid = (l+r)/2;
for(int i=0; i<mid; i++){
if(skip[i]) continue;
a[i] = 1-a[i];
}
if(coba(idx)) l = mid+1; // ada di kanan
else { // ada di kiri
r = mid;
}
for(int i=0; i<mid; i++){ // revert supaya paling depan == idx
if(skip[i]) continue;
a[i] = 1-a[i];
}
}
if(l!=r) assert(false);
con[l] = idx;
if(coba(idx)) ty[l] = a[l];
else ty[l] = 1-a[l];
}
void exploreCave(int N) {
n = N;
for(int i=0; i<n; i++){ // find levernya, up or down
bin(i);
}
answer(con, ty);
}
