#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
const int NMAX = 5000;
int states[NMAX], doors[NMAX], query_states[NMAX];
bool found[NMAX];
bool opens(int ans, int door) {
if(ans == -1)
return true;
return ans > door;
}
void exploreCave(int N) {
for(int i = 0; i < N; ++i) { /// fixez usa
for(int j = 0; j < N; ++j)
if(found[j])
query_states[j] = states[j]; /// continuitatea se mentine pentru ca pana la usa i am aflat raspunsurile, deci ma pot asigura ca pot ajunge cu usi deschise pana aici
else
query_states[j] = 1;
int ans = tryCombination(query_states);
bool switch_state = opens(ans, i); /// aflu ce stare are switch-ul usii
int st = 0, dr = N - 1;
while(st < dr) { /// caut switch-ul
int mid = (st + dr) >> 1;
for(int j = 0; j < N; ++j)
if(found[j]) /// daca switch-ul e de la o usa aflata pana acum procedez analog anterior
query_states[j] = states[j];
else
if(st <= j && j <= mid) /// in prima jumatate pun starea switch-ului usii
query_states[j] = switch_state;
else
query_states[j] = switch_state ^ 1; /// in a doua invers
int ans = tryCombination(query_states);
if(opens(ans, i)) /// daca switch-ul ce deschide usa e in prima jumatate o iau la stanga
dr = mid;
else
st = mid + 1; /// altfel o iau la dreapta
}
/// am gasit switch-ul, deci marchez ca l-am gasit, ce stare are si ce usa actioneaza
found[st] = true, states[st] = switch_state, doors[st] = i;
}
answer(states, doors);
}
