#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int const MAX = 5007;
int guess[MAX];
int comb[MAX];
int link[MAX];
void exploreCave(int N) {
for (int i = 0; i < N; ++i)
comb[i] = link[i] = -1;
for (int gate = 0; gate < N; ++gate) //guessing which gate
{
for (int i = 0; i < N; ++i)
{
if (comb[i] != -1) guess[i] = comb[i];
else guess[i] = 0;
}
int first_closed = tryCombination(guess);
int lt = 0, rt = N-1;
while (lt < rt)
{
int mid = (lt + rt) / 2;
for (int i = 0; i < N; ++i)
{
if (comb[i] != -1) guess[i] = comb[i];
else guess[i] = (i <= mid);
}
int closed = tryCombination(guess);
if ((first_closed == gate) ^ (closed == gate)) rt = mid;
else lt = mid + 1;
/*
cerr << "guess: ";
for (int i = 0; i < N; ++i)
cerr << guess[i] << " ";
cerr << '\n';
cerr << "closed: ";
cerr << closed << '\n';
*/
}
comb[lt] = first_closed == gate;
link[lt] = gate;
//cerr << "switch " << lt << " links gate " << gate << '\n';
//exit(0);
}
answer(comb, link);
}
