#include "cave.h"
#include<vector>
#include<iostream>
using namespace std;
void exploreCave(int N) {
int opens[N]{}; // i-th lock opens door opens[i];
int value[N]{}; // i-th lock must be set to value[i] to open door opens[i]
bool sure[N]{}; // the states for i-th lock are correctly calculated
int combination[N]{};
for(int gate = 0; gate < N; gate ++){
vector<int> cands;
for(int i = 0; i < N; i ++){
if(sure[i]) combination[i] = value[i];
else{
cands.push_back(i);
combination[i] = 1;
}
}
int first_locked = tryCombination(combination);
int key = (first_locked > gate || first_locked == -1);
int low = 0, high = cands.size() - 1, lock = -1;
while(low <= high){
int mid = (low + high) / 2;
for(int i = 0; i < cands.size(); i ++){
if(i <= mid) combination[cands[i]] = key;
else combination[cands[i]] = (key ^ 1);
}
int tmp = tryCombination(combination);
if(tmp > gate || tmp == -1){
lock = cands[mid];
high = mid - 1;
}
else{
low = mid + 1;
}
}
opens[lock] = gate;
value[lock] = key;
sure[lock] = true;
}
answer(value, opens);
}
