#include "cave.h"
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <set>
using namespace std;
void exploreCave(int N) {
vector<int> solved_position (N, -1); //correct position for switch i.
vector<int> solved_door (N, -1); //door switch i is connected to.
for (int current_door = 0; current_door < N; current_door++){
vector<int> unknown_switches;
for (int i = 0; i < N; i++){
if (solved_door[i] == -1){
unknown_switches.push_back(i);
}
}
int current_door_position = 0;
int S[N];
for (int i = 0; i < N; i++){
if (solved_position[i] == -1){
S[i] = 0;
} else {
S[i] = solved_position[i];
}
}
int d = tryCombination(S);
if (d >= 0 && d <= current_door){
current_door_position = 1;
}
int low = 0;
int high = unknown_switches.size() - 1;
//answer in [low, high]
while (high != low){
int mid = (high + low) / 2;
for (int i = 0; i < N; i++){
if (solved_position[i] == -1){
S[i] = current_door_position;
} else {
S[i] = solved_position[i];
}
}
for (int i = low; i <= mid; i++){
S[unknown_switches[i]] = ((current_door_position + 1) % 2);
}
d = tryCombination(S);
if (d == current_door ){
high = mid;
} else {
low = mid + 1;
}
}
solved_door[unknown_switches[low]] = current_door;
solved_position[unknown_switches[low]] = current_door_position;
}
answer(&solved_position[0], &solved_door[0]);
}
