#include "cave.h"
#include <cstdio>
void exploreCave(int N) {
int S[5004];
int D[5004];
int C[5004];
for (int i = 0; i < N; ++i)
S[i] = -1;
for (int i = 0; i < N; ++i)
D[i] = -1;
for (int n = 0; n < N; ++n) {
for (int i = 0; i < N; ++i)
C[i] = S[i] >= 0 ? S[i] : 0;
// fprintf(stderr, "n:%d ", n);
// for (int i = 0; i < N; ++i)
// fprintf(stderr, "%d", C[i]);
// fprintf(stderr, "\n");
int first_closed_door = tryCombination(C);
int is_cur_door_closed = first_closed_door == n;
// fprintf(stderr, "first_closed_door:%d is_cur_door_closed:%d\n",
// first_closed_door, is_cur_door_closed);
int lo = 0, hi = N-1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
for (int i = lo; i <= mid; ++i)
C[i] = S[i] >= 0 ? S[i] : 1;
int door = tryCombination(C);
// fprintf(stderr, "lo:%d hi:%d mid:%d ", lo, hi, mid);
// for (int i = 0; i < N; ++i)
// fprintf(stderr, "%d", C[i]);
// fprintf(stderr, " door:%d\n", door);
if (is_cur_door_closed) {
if (door == n) {
// still closed
lo = mid+1;
}
else {
// door opened
hi = mid;
}
}
else {
if (door != n) {
// still opened
lo = mid+1;
}
else {
// door closed
hi = mid;
}
}
for (int i = lo; i <= mid; ++i)
C[i] = S[i] >= 0 ? S[i] : 0;
}
// fprintf(stderr, "lo:%d\n", lo);
// lo is the switch for door n
D[lo] = n;
S[lo] = is_cur_door_closed ? 1 : 0;
}
answer(S, D);
}
