# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
941657 | 2024-03-09T09:00:32 Z | benjaminkleyn | Finding Routers (IOI20_routers) | C++17 | 4 ms | 780 KB |
#include <bits/stdc++.h> #include "routers.h" using namespace std; map<int, int> mem; int detect(int x) { if (mem.find(x) != mem.end()) return mem[x]; return mem[x] = use_detector(x); } bool check(int x, int i) { if (mem.find(x) != mem.end()) return mem[x] <= i; auto it = prev(mem.upper_bound(x)); return (it->second <= i); } vector<int> find_routers(int l, int n, int q) { l -= l % 2; mem = map<int, int>(); vector<int> ans(n, 0); mem[0] = 0; for (int i = 0, x = 0; i < n - 1; i++) { int prev = x; auto it = mem.find(x); while (next(it) != mem.end() && next(it)->second == i) it = next(it); x = it->first; for (int k = 20; k >= 0; k--) while (x + (1 << k) <= l && check(x + (1 << k), i) && detect(x + (1 << k)) == i) x += (1 << k); ans[i + 1] = x + (x - ans[i]); } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 504 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 1 ms | 344 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 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 | 1 ms | 600 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 344 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 0 ms | 348 KB | Output is correct |
19 | Correct | 0 ms | 348 KB | Output is correct |
20 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 348 KB | Output is correct |
5 | Correct | 1 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 1 ms | 348 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 1 ms | 348 KB | Output is correct |
13 | Correct | 1 ms | 348 KB | Output is correct |
14 | Correct | 1 ms | 348 KB | Output is correct |
15 | Correct | 1 ms | 348 KB | Output is correct |
16 | Correct | 1 ms | 348 KB | Output is correct |
17 | Correct | 1 ms | 348 KB | Output is correct |
18 | Correct | 1 ms | 348 KB | Output is correct |
19 | Correct | 1 ms | 344 KB | Output is correct |
20 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 1 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 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 | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 344 KB | Output is correct |
13 | Correct | 0 ms | 344 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 1 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 1 ms | 348 KB | Output is correct |
19 | Correct | 1 ms | 348 KB | Output is correct |
20 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 604 KB | Output is correct |
2 | Correct | 4 ms | 780 KB | Output is correct |
3 | Correct | 3 ms | 604 KB | Output is correct |
4 | Correct | 4 ms | 604 KB | Output is correct |
5 | Correct | 4 ms | 604 KB | Output is correct |
6 | Correct | 3 ms | 604 KB | Output is correct |
7 | Correct | 3 ms | 604 KB | Output is correct |
8 | Correct | 3 ms | 604 KB | Output is correct |
9 | Correct | 3 ms | 604 KB | Output is correct |
10 | Correct | 3 ms | 600 KB | Output is correct |
11 | Correct | 2 ms | 348 KB | Output is correct |
12 | Correct | 3 ms | 604 KB | Output is correct |
13 | Correct | 2 ms | 348 KB | Output is correct |
14 | Correct | 3 ms | 604 KB | Output is correct |
15 | Correct | 3 ms | 604 KB | Output is correct |
16 | Correct | 3 ms | 604 KB | Output is correct |
17 | Correct | 3 ms | 604 KB | Output is correct |
18 | Correct | 3 ms | 604 KB | Output is correct |
19 | Correct | 3 ms | 736 KB | Output is correct |
20 | Correct | 3 ms | 604 KB | Output is correct |
21 | Correct | 3 ms | 604 KB | Output is correct |