#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int n) {
int top, bottom, middle, result, locans;
int ansvec[n], test[n], matching[n];
bool sus, solved[n];
for (int i=0;i<n;i++) {
solved[i] = false;
}
for (int i=0;i<n;i++) {
top = n-1; bottom = 0;
for (int j=0;j<n;j++) {
if (!solved[j]) {
test[j] = 0;
}
}
result = tryCombination(test);
sus = true;
if (result > i || result == -1) {
sus = false;
}
locans = (int)sus;
sus = true;
while (bottom < top) {
middle = (bottom + top) / 2;
for (int j=bottom;j<=middle;j++) {
if (!solved[j]) {
test[j] = (int)sus;
}
}
//for (int j: test) {cout << j << ' ';}
//cout << '\n';
result = tryCombination(test);
//cout << "b: " << bottom << " t: " << top << " m: " << middle << " res: " << result;
//cout << " sus: " << sus;
//cout << '\n';
if (result == -1) {result = n;}
if ((result > i && (int)sus == locans) || (result == i && (int)sus != locans)) {
top = middle;
sus = !sus;
} else {
bottom = middle + 1;
}
}
//cout << i << ' ' << top << ' ' << locans;
//cout << '\n' << '\n';
solved[top] = true;
ansvec[top] = locans;
test[top] = locans;
matching[top] = i;
}
answer(ansvec, matching);
}
