#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> aux){
int s[aux.size()];
for(int i = 0; i < aux.size(); i++) s[i] = aux[i];
// cerr << "ASK: ";
// for(int i = 0; i < S.size(); i++) cerr << s[i] << ' '; cerr << endl;
int v = tryCombination(s);
// cerr << "Response: " << v << endl;
if(v==-1){
v = n+1;
// S = aux;
}
return v;
// 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;
// cerr << "\nSolving porta " << porta << endl;
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;
//00x0x00x000x11x111x11x1x
//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;
else l = m+1;
}
S[unknown[l]] = 0;
D[unknown[l]] = porta;
}
else{
//se der true, nossa porta fica aberta com 1
//busca binaria no unknown pra encontrar primeiro que der T;
//11x11111x0000x0000x000x00x00
//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[unknown[l]] = 1;
D[unknown[l]] = porta;
}
// cerr << "What we know:\n";
// for(int i : S){
// cerr << (char)(i==-1? 'x' : '0'+i) << ' ';
// }
// cerr << endl;
}
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);
}
