#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int ans[5010]; // ans[switch] = door it controls
int sw[5010]; // switch orientation: 0 = up, 1 = down
int chk[5010]; // whether a switch has been assigned
void exploreCave(int n) {
// Edge case: only 1 switch/door
if(n == 1) {
sw[0] = 0;
if(tryCombination(sw) != -1) sw[0] = 1;
ans[0] = 0;
answer(sw, ans);
return;
}
// Maximum number of bits needed to encode switches
int maxbit = 0;
while((1 << maxbit) < n) maxbit++;
// Process doors from 0 to n-1
for(int door = 0; door < n; door++) {
// Step 1: initialize unknown switches to 0
for(int i = 0; i < n; i++)
if(!chk[i])
sw[i] = 0;
// Step 2: determine correct orientation for door
int curans = (tryCombination(sw) == door) ? 1 : 0;
// Step 3: determine controlling switch using bits
int cursw = 0; // the index of the switch controlling this door
for(int bit = 0; bit < maxbit; bit++) {
for(int i = 0; i < n; i++) {
if(chk[i]) continue; // already assigned
// Inline the bit check instead of havethisbit
if( (i & (1 << bit)) != 0 )
sw[i] = curans;
else
sw[i] = 1 - curans; // opposite orientation
}
// Call grader to see if this flip affects door `door`
if(tryCombination(sw) != door)
cursw |= (1 << bit); // bit is 1 for controlling switch
}
// Step 4: store results
ans[cursw] = door; // switch cursw controls door
sw[cursw] = curans; // set its correct orientation
chk[cursw] = 1; // mark switch as used
}
// Step 5: output final answer
answer(sw, ans);
}
