#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e3 + 10;
int certo[MAXN], atual[MAXN], posCerto[MAXN], alav[MAXN], door[MAXN];
void exploreCave(int N) {
for (int i = 0; i < N; i++) {certo[i] = -1; atual[i] = -1; posCerto[i] = -1; alav[i] = -1; door[i] = -1;}
for (int n = 0; n < N; n++)
{
for (int i = 0; i < N; i++) atual[i] = (posCerto[i] == -1) ? 0 : posCerto[i];
int aux = tryCombination(atual);
if (aux > n || aux == -1) certo[n] = 0;
else certo[n] = 1;
for (int i = 0; i < N; i++) atual[i] = (posCerto[i] == -1) ? certo[n] : posCerto[i];
int ini = 0; int fim = N-1;
while (ini < fim)
{
int m = (ini + fim) / 2;
for (int i = m+1; i <= fim; i++) atual[i] = (posCerto[i] == -1) ? (1 - certo[n]) : posCerto[i];
int aux = tryCombination(atual);
if (aux > n || aux == -1) fim = m;
else ini = m+1;
}
alav[n] = fim;
door[fim] = n;
posCerto[fim] = certo[n];
}
answer(posCerto, door);
}
