# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1048713 | 2024-08-08T09:13:10 Z | Gromp15 | 고대 책들 (IOI17_books) | C++17 | 400 ms | 1048576 KB |
#include <bits/stdc++.h> #include "books.h" #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() using namespace std; template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } template<typename op> struct sparse_table { op x; vector<vector<int>> table; sparse_table(const vector<int>& a, op t) : table(__lg(sz(a)) + 1, vector<int>(sz(a))), x(t) { for (int i = 0; i < sz(a); i++) table[0][i] = a[i]; for (int i = 1; i <= __lg(sz(a)); i++) { for (int j = 0; j < sz(a); j++) { if (j + (1 << i) - 1 >= sz(a)) break; table[i][j] = x(table[i-1][j], table[i-1][j+(1<<(i-1))]); } } } int query(int l, int r) { int h = __lg(r-l+1); return x(table[h][l], table[h][r-(1<<h)+1]); } }; long long minimum_walk(std::vector<int> p, int s) { if (!s) { int n = p.size(); vector<bool> vis(n); vector<long long> cost(n); vector<int> to(n); long long ans = 0; for (int i = 0; i < n; i++) if (i != p[i] && !vis[i]) { int right = i; int tmp = i; while (!vis[tmp]) { ckmax(right, tmp); ans += abs(tmp - p[tmp]), vis[tmp] = 1, tmp = p[tmp]; } to[i] = right; } int on = 0; fill(all(vis), 0); for (int i = 0; i < n; i++) if (i != p[i] && !vis[i]) { int tmp = i; while (!vis[tmp]) vis[tmp] = 1, tmp = p[tmp]; if (i <= on) ckmax(on, to[i]); else ans += 2 * (i - on), on = to[i]; } return ans; } int n = p.size(); vector<int> L(n), R(n); long long ans = 0; vector<bool> vis(n); for (int i = 0; i < n; i++) if (!vis[i]) { int right = i; int tmp = i; vector<int> cur; while (!vis[tmp]) { cur.emplace_back(tmp); ckmax(right, tmp); ans += abs(tmp - p[tmp]), vis[tmp] = 1, tmp = p[tmp]; } for (int v : cur) L[v] = i, R[v] = right; } sparse_table mn(L, [&](int x, int y) { return min(x, y); }); sparse_table mx(R, [&](int x, int y) { return max(x, y); }); vector<vector<long long>> dp(n, vector<long long>(n, 1e18)); dp[s][s] = 0; for (int len = 1; len < n; len++) { for (int l = 0; l+len-1 < n; l++) { int r = l+len-1; ckmin(dp[mn.query(l, r)][mx.query(l, r)], dp[l][r]); if (l) ckmin(dp[l-1][r], dp[l][r] + 2); if (r+1 < n) ckmin(dp[l][r+1], dp[l][r] + 2); } } int l = n, r = -1; for (int i = 0; i < n; i++) if (i != p[i]) ckmin(l, i), r = i; if (l == n) return 0; long long best = 1e18; for (int i = 0; i <= l; i++) for (int j = r; j < n; j++) ckmin(best, dp[i][j]); return best + ans; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | 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 | 0 ms | 424 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 | 344 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 | 344 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 348 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 |
# | 결과 | 실행 시간 | 메모리 | 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 | 0 ms | 424 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 | 344 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 | 344 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 348 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 | 344 KB | Output is correct |
20 | Correct | 0 ms | 348 KB | Output is correct |
21 | Correct | 0 ms | 344 KB | Output is correct |
22 | Correct | 0 ms | 348 KB | Output is correct |
23 | Correct | 0 ms | 348 KB | Output is correct |
24 | Correct | 0 ms | 348 KB | Output is correct |
25 | Correct | 0 ms | 348 KB | Output is correct |
26 | Correct | 0 ms | 348 KB | Output is correct |
27 | Correct | 0 ms | 348 KB | Output is correct |
28 | Correct | 0 ms | 348 KB | Output is correct |
29 | Correct | 0 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | 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 | 0 ms | 424 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 | 344 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 | 344 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 348 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 | 344 KB | Output is correct |
20 | Correct | 0 ms | 348 KB | Output is correct |
21 | Correct | 0 ms | 344 KB | Output is correct |
22 | Correct | 0 ms | 348 KB | Output is correct |
23 | Correct | 0 ms | 348 KB | Output is correct |
24 | Correct | 0 ms | 348 KB | Output is correct |
25 | Correct | 0 ms | 348 KB | Output is correct |
26 | Correct | 0 ms | 348 KB | Output is correct |
27 | Correct | 0 ms | 348 KB | Output is correct |
28 | Correct | 0 ms | 348 KB | Output is correct |
29 | Correct | 0 ms | 348 KB | Output is correct |
30 | Correct | 86 ms | 19968 KB | Output is correct |
31 | Correct | 100 ms | 24892 KB | Output is correct |
32 | Correct | 59 ms | 24788 KB | Output is correct |
33 | Correct | 71 ms | 25048 KB | Output is correct |
34 | Correct | 67 ms | 24832 KB | Output is correct |
35 | Correct | 72 ms | 24976 KB | Output is correct |
36 | Correct | 67 ms | 24824 KB | Output is correct |
37 | Correct | 72 ms | 24960 KB | Output is correct |
38 | Correct | 74 ms | 24916 KB | Output is correct |
39 | Correct | 64 ms | 24736 KB | Output is correct |
40 | Correct | 87 ms | 24932 KB | Output is correct |
41 | Correct | 80 ms | 24788 KB | Output is correct |
42 | Correct | 78 ms | 24992 KB | Output is correct |
43 | Correct | 69 ms | 24992 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 8280 KB | Output is correct |
2 | Correct | 5 ms | 8284 KB | Output is correct |
3 | Correct | 5 ms | 8308 KB | Output is correct |
4 | Correct | 5 ms | 8280 KB | Output is correct |
5 | Correct | 5 ms | 8284 KB | Output is correct |
6 | Correct | 4 ms | 8292 KB | Output is correct |
7 | Correct | 4 ms | 8220 KB | Output is correct |
8 | Correct | 5 ms | 8284 KB | Output is correct |
9 | Correct | 5 ms | 8336 KB | Output is correct |
10 | Correct | 4 ms | 8284 KB | Output is correct |
11 | Correct | 6 ms | 8404 KB | Output is correct |
12 | Correct | 5 ms | 8284 KB | Output is correct |
13 | Correct | 4 ms | 8284 KB | Output is correct |
14 | Correct | 6 ms | 8236 KB | Output is correct |
15 | Correct | 5 ms | 8280 KB | Output is correct |
16 | Correct | 4 ms | 8284 KB | Output is correct |
17 | Correct | 5 ms | 8284 KB | Output is correct |
18 | Correct | 6 ms | 8284 KB | Output is correct |
19 | Correct | 5 ms | 8280 KB | Output is correct |
20 | Correct | 6 ms | 8284 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | 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 | 0 ms | 424 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 | 344 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 | 344 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 348 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 | 344 KB | Output is correct |
20 | Correct | 0 ms | 348 KB | Output is correct |
21 | Correct | 0 ms | 344 KB | Output is correct |
22 | Correct | 0 ms | 348 KB | Output is correct |
23 | Correct | 0 ms | 348 KB | Output is correct |
24 | Correct | 0 ms | 348 KB | Output is correct |
25 | Correct | 0 ms | 348 KB | Output is correct |
26 | Correct | 0 ms | 348 KB | Output is correct |
27 | Correct | 0 ms | 348 KB | Output is correct |
28 | Correct | 0 ms | 348 KB | Output is correct |
29 | Correct | 0 ms | 348 KB | Output is correct |
30 | Correct | 86 ms | 19968 KB | Output is correct |
31 | Correct | 100 ms | 24892 KB | Output is correct |
32 | Correct | 59 ms | 24788 KB | Output is correct |
33 | Correct | 71 ms | 25048 KB | Output is correct |
34 | Correct | 67 ms | 24832 KB | Output is correct |
35 | Correct | 72 ms | 24976 KB | Output is correct |
36 | Correct | 67 ms | 24824 KB | Output is correct |
37 | Correct | 72 ms | 24960 KB | Output is correct |
38 | Correct | 74 ms | 24916 KB | Output is correct |
39 | Correct | 64 ms | 24736 KB | Output is correct |
40 | Correct | 87 ms | 24932 KB | Output is correct |
41 | Correct | 80 ms | 24788 KB | Output is correct |
42 | Correct | 78 ms | 24992 KB | Output is correct |
43 | Correct | 69 ms | 24992 KB | Output is correct |
44 | Correct | 5 ms | 8280 KB | Output is correct |
45 | Correct | 5 ms | 8284 KB | Output is correct |
46 | Correct | 5 ms | 8308 KB | Output is correct |
47 | Correct | 5 ms | 8280 KB | Output is correct |
48 | Correct | 5 ms | 8284 KB | Output is correct |
49 | Correct | 4 ms | 8292 KB | Output is correct |
50 | Correct | 4 ms | 8220 KB | Output is correct |
51 | Correct | 5 ms | 8284 KB | Output is correct |
52 | Correct | 5 ms | 8336 KB | Output is correct |
53 | Correct | 4 ms | 8284 KB | Output is correct |
54 | Correct | 6 ms | 8404 KB | Output is correct |
55 | Correct | 5 ms | 8284 KB | Output is correct |
56 | Correct | 4 ms | 8284 KB | Output is correct |
57 | Correct | 6 ms | 8236 KB | Output is correct |
58 | Correct | 5 ms | 8280 KB | Output is correct |
59 | Correct | 4 ms | 8284 KB | Output is correct |
60 | Correct | 5 ms | 8284 KB | Output is correct |
61 | Correct | 6 ms | 8284 KB | Output is correct |
62 | Correct | 5 ms | 8280 KB | Output is correct |
63 | Correct | 6 ms | 8284 KB | Output is correct |
64 | Runtime error | 400 ms | 1048576 KB | Execution killed with signal 9 |
65 | Halted | 0 ms | 0 KB | - |