| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1284643 | hiddenmeanings | Cave (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
void exploreCave(int N) {
int S[N], D[N];
bool used[N] = {false};
for (int door = 0; door < N; door++) {
int comb[N];
for (int i = 0; i < N; i++) {
comb[i] = used[i] ? S[i] : 0;
}
int l = 0, r = N - 1, switchIndex = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
for (int i = 0; i < N; i++) {
comb[i] = used[i] ? S[i] : 0;
}
for (int i = l; i <= mid; i++) {
if (!used[i]) comb[i] = 1;
}
int result = tryCombination(comb);
if (result == door || result == -1) {
switchIndex = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
comb[switchIndex] = 0;
if (tryCombination(comb) == door) {
comb[switchIndex] = 1;
}
D[switchIndex] = door;
S[switchIndex] = comb[switchIndex];
used[switchIndex] = true;
}
// Prepare arrays to pass to answer()
vector<int> S_out = S;
vector<int> D_out = D;
answer(S_out.data(), D_out.data());
}
