#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "cave.h"
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
void exploreCave(int N) {
int config[N],perm[N];
ordered_set idx;
for(int i=0;i<N;++i) idx.insert(i);
for(int i=0;i<N;++i) {
bool on=1;
for(int x:idx) config[x]=1;
if(tryCombination(config)<=i) on=0;
for(int x:idx) config[x]=!on;
int st=0,sz=(N-i)/2,psz=N-i,sw;
while(sz>0) {
sw=st;
for(int j=st;j<=st+sz;++j) config[*idx.find_by_order(j)]=on;
if(tryCombination(config)<=i) {
st=st+sz;
int tsz=sz;
sz=(psz-sz)/2;
psz=tsz;
} else {
sz/=2;
sw=st;
}
for(int j=st;j<=st+sz;++j) config[*idx.find_by_order(j)]=!on;
}
perm[sw]=i;
config[sw]=on;
idx.erase(sw);
}
answer(perm,config);
}
