#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int NMAX = 5002;
int know[NMAX]; ///know[i] = pozitia buna a switchului i
int who[NMAX]; ///who[i] = switch-ul corespunzator usii i
int door[NMAX]; ///door[i] = usa corespunzatoare switchului i
int M;
int aux[NMAX];
int Check (int ask, int value, int cnt) {
for (int i = 0; i < M; ++ i )
aux[i] = -1;
for (int i = 0; i < ask; ++ i )
aux[who[i]] = know[who[i]];
for (int i = 0; i <= cnt; ++ i )
if (aux[i] == -1) aux[i] = value;
for (int i = cnt+1; i < M; ++ i )
if (aux[i] == -1) aux[i] = 1 - value;
return tryCombination(aux);
}
void exploreCave(int N) {
M = N;
for (int i = 0; i < N; ++ i )
who[i] = know[i] = -1;
for (int i = 0; i < N; ++ i ) {
int switch_state = 1;
int verif = Check(i, 0, N-1);
if (verif == -1 || verif > i) switch_state = 0;
int st = 0, dr = N - 1;
int which_switch = N;
while (st <= dr) {
int mij = (st + dr) / 2;
int verif = Check(i, switch_state, mij);
if (verif == -1 || verif > i) {
which_switch = mij;
dr = mij - 1;
}
else st = mij + 1;
}
who[i] = which_switch;
know[which_switch] = switch_state;
}
for (int i = 0; i < N; ++ i )
door[who[i]] = i;
return answer(know, door);
}
