/*
* With a little appreciation, in a mostly hollow tone, she says, "Delightful." As if the world has any meaning.
* TASK : Cave
* AUTHOR : Marszpace
*/
#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
int swap(int k){
if(k==1){return 0;}
else{return 1;}
}
int find_button(vector<bool>& mask, vector<int>& states, int l, int r, int init, int n){
if(l==r){return l;}
// Find if it's in left or right
int mid=(l+r)/2;
for(int i=l;i<=mid;i++){
if(!mask[i]){
states[i]=swap(states[i]);
}
}
int res=tryCombination(states.data());
for(int i=l;i<=mid;i++){
if(!mask[i]){
states[i]=swap(states[i]);
}
}
if((res==n)==(init==n)){
return find_button(mask,states,mid+1,r,init,n);
}
else{
return find_button(mask,states,l,mid,init,n);
}
}
void exploreCave(int N) {
vector<int> states(N,0);
vector<bool> mask(N,false);
vector<int> links(N,0);
for(int i=0;i<N;i++){
int init=tryCombination(states.data());
int idx=find_button(mask,states,0,N-1,init,i);
states[idx]=(init>i)?0:1;
mask[idx]=true;
links[idx]=i;
}
answer(states.data(),links.data());
}
