# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1214756 | nekolie | Cave (IOI13_cave) | C++20 | 0 ms | 0 KiB |
// When she's prettier than any DP you've ever seen...
#include <bits/stdc++.h>
#include "cave.in"
using namespace std;
void exploreCave(int n) {
int sw[n], open[n], door[n], pom[n];
fill(open,open+n,2);
for (int i = 0; i < n; i++) {
fill(pom,pom+n,0);
for (int j = 0; j < n; j++)
if (open[j] != 2)
pom[j] = open[j];
int ind = tryCombination(pom), l = 0, r = n-1;
sw[i] = ((ind == i) ? 1 : 0);
while (l < r) {
int s = (l+r)/2;
fill(pom,pom+n,sw[i]), fill(pom+l,pom+s+1,(1^sw[i]));
for (int j = 0; j < n; j++)
if (open[j] != 2)
pom[j] = open[j];
ind = tryCombination(pom);
if (ind == i)
r = s;
else
l = s+1;
}
open[l] = sw[i], door[l] = i;
}
answer(open,door);
}