#include "cave.h"
#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
using namespace std;
const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int OFF = (1 << 20);
int bio[5005];
int koji[5005];
int pok[5005];
void promjena(int lo, int mid, int pravi) {
for (int i = lo; i <= mid; i++) {
if (bio[i] == -1) pok[i] = pravi;
}
}
void exploreCave(int n) {
memset(bio, -1, sizeof bio);
for (int i = 0; i < n; i++) {
int pravi = 0;
for (int j = 0; j < n; j++) {
if (bio[j] == -1) pok[j] = 0;
else pok[j] = bio[j];
}
int tren = tryCombination(pok);
if (tren == i) {
pravi = 1;
}
else {
for (int j = 0; j < n; j++) {
if (bio[j] == -1) pok[j] = 1;
}
}
int lo = 0, hi = n-1;
while (lo < hi) {
int mid = (lo + hi) / 2;
promjena(lo, mid, pravi);
int odg = tryCombination(pok);
promjena(lo, mid, 1-pravi);
if (odg == i) {
lo = mid+1;
}
else {
hi = mid;
}
}
bio[lo] = pravi;
koji[i] = lo;
}
answer(bio, koji);
}
