#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
// some sort of binary search or something
// check door i: if next is > door i, then that means door i is open somewhere
// == to i, door i is definitely closed
// how about similar to Dark Ride: We identify it binarily from the bit representation?
// if res == door, at bit i = 1, then for all switches with representation bit i = 1, we onyl have to look at them (shrink by 1/2)
// binary search should be correct...
int doors[5005];
int switches[5005];
int used[5005];
void exploreCave(int n){
if(n == 1){
switches[0] = 0;
if(tryCombination(switches) != -1){
switches[0] = 1;
}
doors[0] = 0;
answer(switches, doors);
return;
}
int maxBit = 0;
while( (1<<maxBit) < n){
maxBit++;
}
for(int door = 0; door < n; door++){
for(int i = 0; i < n; i++){
if(!used[i]){
switches[i] = 0; // maybe this si where we went wrong? Or maybe we shouldv have used array
}
}
int curAns = (tryCombination(switches) == door) ? 1 : 0;
int curSwitch = 0;
for(int k = 0; k < maxBit; k++){
for(int i = 0; i < n; i++){
if(used[i]){
continue;
}
if(i & (1 << k) != 0){
switches[i] = curAns;
}else{
switches[i] = 1 - curAns;
}
}
if(tryCombination(switches) != door){
curSwitch |= (1 << k); // current bit works
}
}
doors[curSwitch] = door;
switches[curSwitch] = curAns;
used[curSwitch] = true;
}
answer(switches, doors);
}
