# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1197202 | SpyrosAliv | Cave (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int tryCombination(int S[]);
void answer(int S[], int D[]);
void exploreCave(int N) {
int n = N;
int corr[n], rep[n];
for (int i = 0; i < n; i++) {
corr[i] = rep[i] = -1;
}
int nxtQ[n];
for (int j = 0; j < n; j++) {
nxtQ[j] = 0;
}
for (int i = 0; i < n; i++) {
bool closed = (tryCombination(nxtQ) == i);
int lo = 0, hi = n-1;
int finIdx = 0;
while (lo <= hi) {
int mid = (lo + hi);
int nxt[n];
for (int j = 0; j < n; j++) nxt[j] = nxtQ[j];
for (int j = 0; j <= mid; j++) {
if (corr[j] == -1) nxt[j] = 1;
}
bool c2 = (tryCombination(nxtQ) == i);
if (c2 == closed) {
hi = mid-1;
}
else {
lo = mid+1;
finIdx = mid;
}
}
rep[i] = finIdx;
if (closed) corr[i] = 1;
else corr[i] = 0;
nxtQ[rep[i]] = corr[i];
}
answer(rep, corr);
}