#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> S, D; //S: correct position, D[i]: door connected by switch i
void _answer(vector<int> S, vector<int> D){
int s[n], d[n];
for(int i = 0; i < S.size(); i++) s[i] = S[i];
for(int i = 0; i < D.size(); i++) d[i] = D[i];
answer(s, d);
}
int _tryCombination(vector<int> S){
int s[S.size()];
for(int i = 0; i < S.size(); i++) s[i] = S[i];
return tryCombination(s);
}
//encontra primeiro switch que muda porta e seu estado
void bsearch(int porta){
//abre todas porta conhecidos,
vector<int> guess = S, unknown;
int verdic;
for(int i = 0; i < n; i++){
if(guess[i] == -1){
guess[i] = 0;
unknown.push_back(i);
}
}
// 1 query para saber se switch deve ser aberto ou n
verdic = _tryCombination(guess);
// 13 query para saber onde esta esse switch
if(verdic > porta){
//se der true, nossa porta fica aberta com 0
//busca binaria no unknown pra encontrar primeiro que der false;
//000000000001111111111111
//TTTTTTFFFFFFFFFFFFFFFFFF
//esse ^ daqui eh nosso switch
int l = 0, r = unknown.size()-1;
while(l < r){
int m = (l+r)/2;
for(int i = 0; i <= m; i++) guess[unknown[i]] = 0;
for(int i = m+1; i < unknown.size(); i++) guess[unknown[i]] = 1;
verdic = _tryCombination(guess);
if(verdic > porta) r = m; //porta esta no intervalo [0, m]
else l = m+1; //porta esta no intervalo [m+1, fim]
}
S[l] = 0;
D[l] = porta;
}
else{
//se der true, nossa porta fica aberta com 1
//busca binaria no unknown pra encontrar primeiro que der T;
//1111111100000000000000000000
//TTTTTTFFFFFFFFFFFFFFFFFF
//esse ^ daqui eh nosso switch
int l = 0, r = unknown.size()-1;
while(l < r){
int m = (l+r)/2;
for(int i = 0; i <= m; i++) guess[unknown[i]] = 1;
for(int i = m+1; i < unknown.size(); i++) guess[unknown[i]] = 0;
verdic = _tryCombination(guess);
if(verdic > porta) r = m; //porta esta no intervalo [0, m]
else l = m+1; //porta esta no intervalo [m+1, fim]
}
S[l] = 1;
D[l] = porta;
}
}
void exploreCave(int N) {
n = N;
S.assign(N, -1);
D.assign(N, -1);
for(int i = 0; i < n; i++){
bsearch(i);
}
_answer(S, D);
}
