#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int tryCombination(int S[]);
void answer(int S[], int D[]);
void exploreCave(int n) {
int res[n];
int state[n];
for (int i = 0;i < n;i++) {
state[i] = -1;
res[i] = -1;
}
int temp[n];
for (int i = 0;i < n;i++) {
int onstate = -1;
for (int j = 0;j < n;j++) {
if (state[j] == -1) temp[j] = 0;
else temp[j] = state[j];
}
int block = tryCombination(temp);
if (block > i || block == -1) {
onstate = 0;
}
else {
onstate = 1;
}
int l = -1, r = n;
while (l + 1 < r) {
int mid = (l + r) / 2;
for (int j = 0;j <= mid;j++) {
if (state[j] == -1) temp[j] = onstate;
else temp[j] = state[j];
}
for (int j = mid + 1;j < n;j++) {
if (state[j] == -1) temp[j] = 1 - onstate;
else temp[j] = state[j];
}
block = tryCombination(temp);
if (block > i || block == -1) {
r = mid;
}
else {
l = mid;
}
}
state[r] = onstate;
res[r] = i;
}
answer(state, res);
}
