#include "cave.h"
#include <vector>
#include <algorithm>
void exploreCave(int N) {
int S[N], D[N], current_S[N];
int real_S[N], real_D[N]; // Yakuniy javoblar uchun
bool found[N]; // Kalit ishlatilganini tekshirish uchun
for (int i = 0; i < N; i++) {
found[i] = false;
real_D[i] = -1;
}
for (int i = 0; i < N; i++) {
// i-chi eshikni ochadigan kalitni va uning holatini topamiz
for (int j = 0; j < N; j++) {
if (found[j]) current_S[j] = real_S[j];
else current_S[j] = 0;
}
int res = tryCombination(current_S);
int target_state;
// Agar res == i bo'lsa, eshik yopiq (holat 1 bo'lishi kerak)
// Agar res > i yoki res == -1 bo'lsa, eshik ochiq (holat 0 ekan)
if (res == -1 || res > i) target_state = 0;
else target_state = 1;
// Ikkilik qidiruv orqali qaysi kalit ekanini topamiz
int low = 0, high = N - 1, key_pos = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
for (int j = 0; j < N; j++) {
if (found[j]) current_S[j] = real_S[j];
else if (j >= low && j <= mid) current_S[j] = target_state;
else current_S[j] = 1 - target_state;
}
int res2 = tryCombination(current_S);
if (res2 == -1 || res2 > i) {
key_pos = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
real_S[key_pos] = target_state;
real_D[key_pos] = i;
found[key_pos] = true;
}
answer(real_S, real_D);
}
