| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1012985 |
2024-07-03T04:10:45 Z |
thangdz2k7 |
Game (APIO22_game) |
C++17 |
|
1212 ms |
87848 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int l[N], r[N], K;
vector <int> in[N], out[N];
void init(int n, int k){
K = k;
for (int i = 0; i <= k; ++ i) l[i] = i, r[i] = i + 1;
for (int i = k + 1; i <= n; ++ i) l[i] = 0, r[i] = k + 1;
for (int i = 0; i <= n; ++ i) in[i] = {}, out[i] = {};
}
int calc(int u, int v){
if (r[u] <= l[v]) return 0;
if (l[u] >= r[v]) return 1;
if (l[u] == l[v] && r[u] == r[v]) return 0;
if (r[v] <= (l[u] + r[u]) / 2){
r[u] = (l[u] + r[u]) / 2;
for (int i : in[u]) if (calc(u, i)) return 1;
for (int i : out[u]) if (calc(i, u)) return 1;
}
else if (l[u] >= (l[v] + r[v]) / 2){
l[v] = (l[v] + r[v]) / 2;
for (int i : in[v]) if (calc(v, i)) return 1;
for (int i : out[v]) if (calc(i, v)) return 1;
}
return 0;
}
int add_teleporter(int u, int v){
++ u;
if (v >= K) ++ v;
in[u].push_back(v);
out[v].push_back(u);
return calc(u, v);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
14424 KB |
Output is correct |
| 2 |
Correct |
5 ms |
14424 KB |
Output is correct |
| 3 |
Correct |
5 ms |
14424 KB |
Output is correct |
| 4 |
Correct |
6 ms |
14388 KB |
Output is correct |
| 5 |
Correct |
7 ms |
14424 KB |
Output is correct |
| 6 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 7 |
Correct |
7 ms |
14424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
14424 KB |
Output is correct |
| 2 |
Correct |
5 ms |
14424 KB |
Output is correct |
| 3 |
Correct |
5 ms |
14424 KB |
Output is correct |
| 4 |
Correct |
6 ms |
14388 KB |
Output is correct |
| 5 |
Correct |
7 ms |
14424 KB |
Output is correct |
| 6 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 7 |
Correct |
7 ms |
14424 KB |
Output is correct |
| 8 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 9 |
Correct |
5 ms |
14424 KB |
Output is correct |
| 10 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 11 |
Correct |
5 ms |
14424 KB |
Output is correct |
| 12 |
Correct |
5 ms |
14296 KB |
Output is correct |
| 13 |
Correct |
8 ms |
14424 KB |
Output is correct |
| 14 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 15 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 16 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 17 |
Correct |
7 ms |
14424 KB |
Output is correct |
| 18 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 19 |
Correct |
7 ms |
14424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
14424 KB |
Output is correct |
| 2 |
Correct |
5 ms |
14424 KB |
Output is correct |
| 3 |
Correct |
5 ms |
14424 KB |
Output is correct |
| 4 |
Correct |
6 ms |
14388 KB |
Output is correct |
| 5 |
Correct |
7 ms |
14424 KB |
Output is correct |
| 6 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 7 |
Correct |
7 ms |
14424 KB |
Output is correct |
| 8 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 9 |
Correct |
5 ms |
14424 KB |
Output is correct |
| 10 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 11 |
Correct |
5 ms |
14424 KB |
Output is correct |
| 12 |
Correct |
5 ms |
14296 KB |
Output is correct |
| 13 |
Correct |
8 ms |
14424 KB |
Output is correct |
| 14 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 15 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 16 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 17 |
Correct |
7 ms |
14424 KB |
Output is correct |
| 18 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 19 |
Correct |
7 ms |
14424 KB |
Output is correct |
| 20 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 21 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 22 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 23 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 24 |
Correct |
6 ms |
14440 KB |
Output is correct |
| 25 |
Correct |
9 ms |
14424 KB |
Output is correct |
| 26 |
Correct |
7 ms |
14584 KB |
Output is correct |
| 27 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 28 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 29 |
Correct |
8 ms |
14680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
14424 KB |
Output is correct |
| 2 |
Correct |
5 ms |
14424 KB |
Output is correct |
| 3 |
Correct |
5 ms |
14424 KB |
Output is correct |
| 4 |
Correct |
6 ms |
14388 KB |
Output is correct |
| 5 |
Correct |
7 ms |
14424 KB |
Output is correct |
| 6 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 7 |
Correct |
7 ms |
14424 KB |
Output is correct |
| 8 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 9 |
Correct |
5 ms |
14424 KB |
Output is correct |
| 10 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 11 |
Correct |
5 ms |
14424 KB |
Output is correct |
| 12 |
Correct |
5 ms |
14296 KB |
Output is correct |
| 13 |
Correct |
8 ms |
14424 KB |
Output is correct |
| 14 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 15 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 16 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 17 |
Correct |
7 ms |
14424 KB |
Output is correct |
| 18 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 19 |
Correct |
7 ms |
14424 KB |
Output is correct |
| 20 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 21 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 22 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 23 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 24 |
Correct |
6 ms |
14440 KB |
Output is correct |
| 25 |
Correct |
9 ms |
14424 KB |
Output is correct |
| 26 |
Correct |
7 ms |
14584 KB |
Output is correct |
| 27 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 28 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 29 |
Correct |
8 ms |
14680 KB |
Output is correct |
| 30 |
Correct |
14 ms |
15856 KB |
Output is correct |
| 31 |
Correct |
9 ms |
14936 KB |
Output is correct |
| 32 |
Correct |
21 ms |
20720 KB |
Output is correct |
| 33 |
Correct |
15 ms |
16472 KB |
Output is correct |
| 34 |
Correct |
26 ms |
24664 KB |
Output is correct |
| 35 |
Correct |
41 ms |
17488 KB |
Output is correct |
| 36 |
Correct |
36 ms |
16720 KB |
Output is correct |
| 37 |
Correct |
36 ms |
17016 KB |
Output is correct |
| 38 |
Correct |
28 ms |
16216 KB |
Output is correct |
| 39 |
Correct |
30 ms |
16432 KB |
Output is correct |
| 40 |
Correct |
45 ms |
26636 KB |
Output is correct |
| 41 |
Correct |
41 ms |
17744 KB |
Output is correct |
| 42 |
Correct |
37 ms |
18000 KB |
Output is correct |
| 43 |
Correct |
39 ms |
17744 KB |
Output is correct |
| 44 |
Correct |
36 ms |
18768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
14424 KB |
Output is correct |
| 2 |
Correct |
5 ms |
14424 KB |
Output is correct |
| 3 |
Correct |
5 ms |
14424 KB |
Output is correct |
| 4 |
Correct |
6 ms |
14388 KB |
Output is correct |
| 5 |
Correct |
7 ms |
14424 KB |
Output is correct |
| 6 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 7 |
Correct |
7 ms |
14424 KB |
Output is correct |
| 8 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 9 |
Correct |
5 ms |
14424 KB |
Output is correct |
| 10 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 11 |
Correct |
5 ms |
14424 KB |
Output is correct |
| 12 |
Correct |
5 ms |
14296 KB |
Output is correct |
| 13 |
Correct |
8 ms |
14424 KB |
Output is correct |
| 14 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 15 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 16 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 17 |
Correct |
7 ms |
14424 KB |
Output is correct |
| 18 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 19 |
Correct |
7 ms |
14424 KB |
Output is correct |
| 20 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 21 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 22 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 23 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 24 |
Correct |
6 ms |
14440 KB |
Output is correct |
| 25 |
Correct |
9 ms |
14424 KB |
Output is correct |
| 26 |
Correct |
7 ms |
14584 KB |
Output is correct |
| 27 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 28 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 29 |
Correct |
8 ms |
14680 KB |
Output is correct |
| 30 |
Correct |
14 ms |
15856 KB |
Output is correct |
| 31 |
Correct |
9 ms |
14936 KB |
Output is correct |
| 32 |
Correct |
21 ms |
20720 KB |
Output is correct |
| 33 |
Correct |
15 ms |
16472 KB |
Output is correct |
| 34 |
Correct |
26 ms |
24664 KB |
Output is correct |
| 35 |
Correct |
41 ms |
17488 KB |
Output is correct |
| 36 |
Correct |
36 ms |
16720 KB |
Output is correct |
| 37 |
Correct |
36 ms |
17016 KB |
Output is correct |
| 38 |
Correct |
28 ms |
16216 KB |
Output is correct |
| 39 |
Correct |
30 ms |
16432 KB |
Output is correct |
| 40 |
Correct |
45 ms |
26636 KB |
Output is correct |
| 41 |
Correct |
41 ms |
17744 KB |
Output is correct |
| 42 |
Correct |
37 ms |
18000 KB |
Output is correct |
| 43 |
Correct |
39 ms |
17744 KB |
Output is correct |
| 44 |
Correct |
36 ms |
18768 KB |
Output is correct |
| 45 |
Correct |
179 ms |
28188 KB |
Output is correct |
| 46 |
Correct |
10 ms |
17292 KB |
Output is correct |
| 47 |
Correct |
11 ms |
17144 KB |
Output is correct |
| 48 |
Correct |
257 ms |
41876 KB |
Output is correct |
| 49 |
Correct |
168 ms |
35680 KB |
Output is correct |
| 50 |
Correct |
379 ms |
87848 KB |
Output is correct |
| 51 |
Correct |
646 ms |
49116 KB |
Output is correct |
| 52 |
Correct |
434 ms |
35572 KB |
Output is correct |
| 53 |
Correct |
620 ms |
35568 KB |
Output is correct |
| 54 |
Correct |
691 ms |
35728 KB |
Output is correct |
| 55 |
Correct |
962 ms |
36400 KB |
Output is correct |
| 56 |
Correct |
1212 ms |
35580 KB |
Output is correct |
| 57 |
Correct |
363 ms |
29780 KB |
Output is correct |
| 58 |
Correct |
344 ms |
29644 KB |
Output is correct |
| 59 |
Correct |
381 ms |
29792 KB |
Output is correct |
| 60 |
Correct |
410 ms |
29652 KB |
Output is correct |
| 61 |
Correct |
501 ms |
29172 KB |
Output is correct |
| 62 |
Correct |
259 ms |
37104 KB |
Output is correct |
| 63 |
Correct |
299 ms |
37368 KB |
Output is correct |
| 64 |
Correct |
944 ms |
66140 KB |
Output is correct |
| 65 |
Correct |
344 ms |
34916 KB |
Output is correct |
| 66 |
Correct |
247 ms |
30840 KB |
Output is correct |
| 67 |
Correct |
573 ms |
53164 KB |
Output is correct |
| 68 |
Correct |
142 ms |
26300 KB |
Output is correct |
| 69 |
Correct |
39 ms |
20584 KB |
Output is correct |
| 70 |
Correct |
523 ms |
47532 KB |
Output is correct |
| 71 |
Correct |
216 ms |
29096 KB |
Output is correct |
| 72 |
Correct |
140 ms |
25012 KB |
Output is correct |
| 73 |
Correct |
402 ms |
40956 KB |
Output is correct |
| 74 |
Correct |
1080 ms |
35364 KB |
Output is correct |
| 75 |
Correct |
671 ms |
43104 KB |
Output is correct |
| 76 |
Correct |
772 ms |
46092 KB |
Output is correct |
