#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
/* ... */
vector<int>ne_najdeni; // SWITCHOVI KOI NE SE DOZNAENI
vector<int>najdeni; // SWITCHOVI KOI SE DOZNAENI
int Match[N]; // SWITCH - > VRATA
int P[N]; // SOSTOJBA NA SWITCH
for (int i = 0; i < N; i++){
ne_najdeni.push_back(i);
}
for (int i = 0; i < N; i++){
//PROBUVAME DA JA OTVORIME I-TATA VRATA
int S[N];
for (int j : najdeni){
S[j] = P[j];
}
//SEGA SME GI OTVORILE SITE VRATI PRED I
for (int j : ne_najdeni){
S[j] = 1;
}
int key = 1;
int resp = tryCombination(S);
if (resp == i){
//ovaa vrata e seuste zaklucena, znaci se otklucuva so 0
key ^= 1;
for (int j : ne_najdeni){
S[j] = key;
}
}
int l = 0, r = (int)ne_najdeni.size() - 1;
while(l<=r){
int mid = (l+r) / 2;
for (int j = 0 ; j < mid; j++){
S[ne_najdeni[j]] = !key;
}
for (int j = mid; j < (int)ne_najdeni.size(); j++){
S[ne_najdeni[j]] = key;
}
resp = tryCombination(S);
if (resp == i){
//zaklucena e seuste
//prosiri
r = mid - 1;
}else{
//otklucena e
l = mid + 1;//zatesni
}
}
P[l-1]=key;
najdeni.push_back(l-1);
sort(najdeni.begin(),najdeni.end());
Match[l-1]=i;
vector<int>nov;
for (int j : ne_najdeni){
if (j == l - 1)continue;
nov.push_back(j);
}
ne_najdeni = nov;
sort(ne_najdeni.begin(),ne_najdeni.end());
}
answer(P,Match);
}
