#include "cave.h"
#include <vector>
#include <cstring>
#include <iostream>
void exploreCave(int N) {
/* ok */
bool vis[N] = {};
int call[N] = {}, ans[N] = {}, connect[N];
bool curdoor;
int l, r, mid;
std::vector<int> possibledoors;
for(int i=0;i<N;i++) possibledoors.push_back(i);
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
if(vis[j]) call[j] = ans[j];
else call[j] = 0;
}
if(tryCombination(call) == i) curdoor = 1;
else curdoor = 0;
l = 0; r = possibledoors.size()-1;
while(l < r) {
mid = (l+r) >> 1;
for(int j=0;j<N;j++) {
if(vis[j]) call[j] = ans[j];
else {
if(possibledoors[l]<=j && j<=possibledoors[mid]) call[j] = curdoor;
else call[j] = !curdoor;
}
}
if(tryCombination(call) != i) r = mid;
else l = mid + 1;
}
int e = possibledoors[l];
//std::cout << "switch " << e << " controls door " << i << '\n';
connect[e] = i; vis[e] = 1; ans[e] = curdoor;
possibledoors.erase(possibledoors.begin()+l);
}
answer(ans, connect);
}
