# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
965297 |
2024-04-18T09:50:42 Z |
IBory |
Cave (IOI13_cave) |
C++17 |
|
234 ms |
832 KB |
#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX = 5005;
int C[MAX], S[MAX], D[MAX];
void exploreCave(int N) {
for (int n = 0; n < N; ++n) {
memset(C, 0x3f, sizeof(C));
vector<int> cand;
for (int p = 0; p < n; ++p) C[D[p]] = S[D[p]];
for (int i = 0; i < N; ++i) {
if (1e9 < C[i]) {
cand.push_back(i);
C[i] = 0;
}
}
int init = tryCombination(C) != n;
if (cand.size() == 1) {
D[n] = cand[0];
S[D[n]] = !init;
break;
}
int l = -1, r = cand.size() - 1;
while (l + 1 < r) {
int mid = (l + r) >> 1;
for (int i = 0; i <= mid; ++i) C[cand[i]] = 1;
int go = tryCombination(C) != n;
(init == go ? l : r) = mid;
for (int i = 0; i <= mid; ++i) C[cand[i]] = 0;
}
D[n] = cand[r];
S[D[n]] = !init;
D[cand[r]] = n;
}
answer(S, D);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
111 ms |
800 KB |
Output is correct |
2 |
Correct |
108 ms |
576 KB |
Output is correct |
3 |
Correct |
169 ms |
584 KB |
Output is correct |
4 |
Correct |
114 ms |
572 KB |
Output is correct |
5 |
Correct |
176 ms |
580 KB |
Output is correct |
6 |
Correct |
174 ms |
584 KB |
Output is correct |
7 |
Correct |
169 ms |
568 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
183 ms |
584 KB |
Output is correct |
13 |
Correct |
168 ms |
576 KB |
Output is correct |
14 |
Correct |
160 ms |
588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
173 ms |
572 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
234 ms |
832 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Incorrect |
190 ms |
348 KB |
Answer is wrong |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
600 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Incorrect |
0 ms |
348 KB |
Answer is wrong |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
600 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Incorrect |
0 ms |
348 KB |
Answer is wrong |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
111 ms |
800 KB |
Output is correct |
2 |
Correct |
108 ms |
576 KB |
Output is correct |
3 |
Correct |
169 ms |
584 KB |
Output is correct |
4 |
Correct |
114 ms |
572 KB |
Output is correct |
5 |
Correct |
176 ms |
580 KB |
Output is correct |
6 |
Correct |
174 ms |
584 KB |
Output is correct |
7 |
Correct |
169 ms |
568 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
183 ms |
584 KB |
Output is correct |
13 |
Correct |
168 ms |
576 KB |
Output is correct |
14 |
Correct |
160 ms |
588 KB |
Output is correct |
15 |
Correct |
173 ms |
572 KB |
Output is correct |
16 |
Correct |
0 ms |
344 KB |
Output is correct |
17 |
Correct |
234 ms |
832 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Incorrect |
190 ms |
348 KB |
Answer is wrong |
21 |
Halted |
0 ms |
0 KB |
- |