#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 5005;
#define FOR(i, x, n) for (int i = x; i <= n; i++)
#define mem(a, x) memset(a, x, sizeof(a))
int s[INF], d[INF];
bool done[INF];
void exploreCave(int n) {
FOR(i, 0, n - 1) {
FOR(j, 0, n - 1) {
if (!done[j]) s[j] = 1;
}
int closed = tryCombination(s);
bool up = closed > i || closed == -1;
FOR(j, 0, n - 1) {
if (!done[j]) s[j] = !up;
}
int pos = -1;
int l = 0, r = n - 1;
while (l <= r) {
int m = (l + r) / 2;
FOR(j, l, m) {
if (!done[j]) s[j] = up;
}
closed = tryCombination(s);
FOR(j, l, m) {
if (!done[j]) s[j] = !up;
}
if (closed > i || closed == -1) {
pos = m;
r = m - 1;
} else {
l = m + 1;
}
}
done[pos] = true;
s[pos] = up;
d[pos] = i;
}
answer(s, d);
}
/*
* 70,000 queries = 5,000 * log2(5,000)
* O(NlogN)
* Once you solve a door in order, query it correctly
* so it basically doesn't exist anymore.
*
* Subtask 1: Just try all 1 or all 0 to find the correct
* switch orientation
* Subtask 2: Split half one into all correct and the other
* into all wrong. If half one opens, that's the new range.
* If half one doesn't, half two is the new range.
*
* Combine these two subtasks to get the final answer
*/
//
