| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 571998 | Vanilla | Cave (IOI13_cave) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int n) {
int s[n], dr[n];
if (n == 1) {
s[0] = dr[0] = 0;
if (tryCombination(s) != -1) {
s[0] = 1;
}
answer(s, dr);
return;
}
for (int i = 0; i < n; i++){
s[i] = 0, dr[i] = -1;
}
for (int door = 0; door < n; door++){
for (int i = 0; i < n; i++){
if (dr[i] == -1) {
s[i] = 0;
}
}
int l = 0, r = n-1, state = 1, k = tryCombination(s);
int rs = 0;
while (l <= r) {
if(k != -1 && k <= door)
for (int i = l; i <= r; i++){
if (dr[i] == -1) s[i] = 0;
}
int mid = (l + r) / 2;
for (int i = l; i <= mid; i++){
if (dr[i] == -1) dr[i] = !dr[i]
}
k = tryCombination(s);
if(k == door) {
r = mid - 1;
rs = mid;
state = !state;
}else {
l = mid + 1;
}
}
dr[rs] = door;
s[rs] = state;
}
answer(s, dr);
}