#include "cave.h"
#include <vector>
#include <iostream>
using namespace std;
void flip(int ask[], int ans[], int start, int end) {
while(start != end) {
if(ans[start] == -1)
ask[start] ^= 1;
start++;
}
}
void unset(int ask[], int ans[], int start, int end) {
while(start != end) {
if(ans[start] == -1)
ask[start] = 0;
start++;
}
}
void exploreCave(int N) {
int ans[N];
int ask[N];
int corr[N];
for(int i = 0; i < N; ++i) {
ans[i] = -1, ask[i] = 0, corr[i] = 0;
}
// per ogni porta
for(int i = 0; i < N; ++i) {
unset(ask, ans, 0, N); // imposta a 0, ignorando le risposte gia' trovate
int q = tryCombination(ask);
bool state = 0;
if(q <= i && q != -1) {
// porta aperta
state = 1;
flip(ask, ans, 0, N);
}
// cambia lo stato di tutte le luci che non influenzano la porta corrente
int l = 0, r = N;
while(r - l > 1) {
int m = (l + r) / 2;
// cambia la sinistra
flip(ask, ans, l, m);
q = tryCombination(ask);
if(q > i || q == -1) {
// la porta e' ancora aperta
l = m;
} else {
// la porta e' chiusa, flippa i range
flip(ask, ans, l, r);
r = m;
}
}
ans[l] = i;
corr[l] = state;
}
answer(corr, ans);
}
