# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
529009 | lcs147 | Cave (IOI13_cave) | C++17 | 719 ms | 580 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) {
vector<int>correct(n, -1), switch_door(n, -1);
for(int i=0; i<n; i++) {
vector<int>s = correct;
for(int &x:s) if(x == -1) x = 1;
int ret = tryCombination(s.data());
int open = -1;
if(ret == -1 || ret > i) {
open = 1;
} else {
open = 0;
}
vector<int>dknow;
for(int j=0; j<n; j++) {
if(correct[j] == -1) {
dknow.push_back(j);
}
}
auto check = [&](int l, int r) {
s = correct;
for(int j=0; j<dknow.size(); j++) {
int id = dknow[j];
if(j < l || j > r) s[id] = !open;
else s[id] = open;
}
ret = tryCombination(s.data());
return ret == -1 || ret > i;
};
int l = 0, r = dknow.size()-1, id = -1;
while(l <= r) {
int m = (l+r)/2;
if(check(l, m)) {
id = m;
r = m - 1;
} else l = m + 1;
}
id = dknow[id];
switch_door[id] = i;
correct[id] = open;
}
answer(correct.data(), switch_door.data());
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |