#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
int n = N;
int correctPosition[n];
int connectedDoor[n];
int tryCombinationArray[n];
for(int i = 0; i < n; ++i) {
correctPosition[i] = -1;
connectedDoor[i] = -1;
tryCombinationArray[i] = 0;
}
for(int i = 0; i < n; ++i) {
int swappedTo[n];
for(int j = 0; j < n; ++j) {
swappedTo[j] = 0;
if(correctPosition[j] == -1) {
tryCombinationArray[j] = 0;
} else {
tryCombinationArray[j] = correctPosition[j];
}
}
int pos = tryCombination(tryCombinationArray);
if(pos == i) pos = 1;
else pos = 0;
int l = 0, r = n;
while(l < r - 1) {
int ce = (l + r) / 2;
for(int j = l; j < ce; ++j) {
swappedTo[j] = 1 - swappedTo[j];
if(correctPosition[j] == -1) {
tryCombinationArray[j] = swappedTo[j];
} else {
tryCombinationArray[j] = correctPosition[j];
}
}
int result = tryCombination(tryCombinationArray);
if(((pos == swappedTo[l]) && (result != i)) || ((pos != swappedTo[l]) && (result == i))) {
r = ce;
} else {
l = ce;
}
}
connectedDoor[l] = i;
correctPosition[l] = pos;
}
answer(correctPosition, connectedDoor);
}
