oj.uz

Submission #1048709

# Submission time Handle Problem Language Result Execution time Memory
1048709 2024-08-08T09:12:24 Z Gromp15 Ancient Books (IOI17_books) C++17
42 / 100
 387 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) {
	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

books.cpp: In instantiation of 'sparse_table<op>::sparse_table(const std::vector<int>&, op) [with op = minimum_walk(std::vector<int>, int)::<lambda(int, int)>]':
books.cpp:43:60:   required from here
books.cpp:12:22: warning: 'sparse_table<minimum_walk(std::vector<int>, int)::<lambda(int, int)> >::table' will be initialized after [-Wreorder]
   12 |  vector<vector<int>> table;
      |                      ^~~~~
books.cpp:11:5: warning:   'minimum_walk(std::vector<int>, int)::<lambda(int, int)> sparse_table<minimum_walk(std::vector<int>, int)::<lambda(int, int)> >::x' [-Wreorder]
   11 |  op x;
      |     ^
books.cpp:13:2: warning:   when initialized here [-Wreorder]
   13 |  sparse_table(const vector<int>& a, op t) : table(__lg(sz(a)) + 1, vector<int>(sz(a))), x(t) {
      |  ^~~~~~~~~~~~
books.cpp: In instantiation of 'sparse_table<op>::sparse_table(const std::vector<int>&, op) [with op = minimum_walk(std::vector<int>, int)::<lambda(int, int)>]':
books.cpp:44:60:   required from here
books.cpp:12:22: warning: 'sparse_table<minimum_walk(std::vector<int>, int)::<lambda(int, int)> >::table' will be initialized after [-Wreorder]
   12 |  vector<vector<int>> table;
      |                      ^~~~~
books.cpp:11:5: warning:   'minimum_walk(std::vector<int>, int)::<lambda(int, int)> sparse_table<minimum_walk(std::vector<int>, int)::<lambda(int, int)> >::x' [-Wreorder]
   11 |  op x;
      |     ^
books.cpp:13:2: warning:   when initialized here [-Wreorder]
   13 |  sparse_table(const vector<int>& a, op t) : table(__lg(sz(a)) + 1, vector<int>(sz(a))), x(t) {
      |  ^~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 348 KB Output is correct
6 Correct 1 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 1 ms 348 KB Output is correct
11 Correct 0 ms 348 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 344 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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 348 KB Output is correct
6 Correct 1 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 1 ms 348 KB Output is correct
11 Correct 0 ms 348 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 344 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 4 ms 8284 KB Output is correct
20 Correct 5 ms 8284 KB Output is correct
21 Correct 7 ms 8284 KB Output is correct
22 Correct 4 ms 8404 KB Output is correct
23 Correct 4 ms 8340 KB Output is correct
24 Correct 5 ms 8284 KB Output is correct
25 Correct 4 ms 8408 KB Output is correct
26 Correct 4 ms 8404 KB Output is correct
27 Correct 5 ms 8284 KB Output is correct
28 Correct 5 ms 8296 KB Output is correct
29 Correct 5 ms 8180 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 348 KB Output is correct
6 Correct 1 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 1 ms 348 KB Output is correct
11 Correct 0 ms 348 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 344 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 4 ms 8284 KB Output is correct
20 Correct 5 ms 8284 KB Output is correct
21 Correct 7 ms 8284 KB Output is correct
22 Correct 4 ms 8404 KB Output is correct
23 Correct 4 ms 8340 KB Output is correct
24 Correct 5 ms 8284 KB Output is correct
25 Correct 4 ms 8408 KB Output is correct
26 Correct 4 ms 8404 KB Output is correct
27 Correct 5 ms 8284 KB Output is correct
28 Correct 5 ms 8296 KB Output is correct
29 Correct 5 ms 8180 KB Output is correct
30 Runtime error 387 ms 1048576 KB Execution killed with signal 9
31 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8284 KB Output is correct
2 Correct 5 ms 8412 KB Output is correct
3 Correct 5 ms 8404 KB Output is correct
4 Correct 5 ms 8284 KB Output is correct
5 Correct 5 ms 8284 KB Output is correct
6 Correct 5 ms 8284 KB Output is correct
7 Correct 5 ms 8284 KB Output is correct
8 Correct 5 ms 8284 KB Output is correct
9 Correct 4 ms 8284 KB Output is correct
10 Correct 5 ms 8284 KB Output is correct
11 Correct 5 ms 8284 KB Output is correct
12 Correct 8 ms 8284 KB Output is correct
13 Correct 5 ms 8396 KB Output is correct
14 Correct 5 ms 8284 KB Output is correct
15 Correct 5 ms 8284 KB Output is correct
16 Correct 5 ms 8280 KB Output is correct
17 Correct 7 ms 8412 KB Output is correct
18 Correct 5 ms 8324 KB Output is correct
19 Correct 5 ms 8284 KB Output is correct
20 Correct 4 ms 8408 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 348 KB Output is correct
6 Correct 1 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 1 ms 348 KB Output is correct
11 Correct 0 ms 348 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 344 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 4 ms 8284 KB Output is correct
20 Correct 5 ms 8284 KB Output is correct
21 Correct 7 ms 8284 KB Output is correct
22 Correct 4 ms 8404 KB Output is correct
23 Correct 4 ms 8340 KB Output is correct
24 Correct 5 ms 8284 KB Output is correct
25 Correct 4 ms 8408 KB Output is correct
26 Correct 4 ms 8404 KB Output is correct
27 Correct 5 ms 8284 KB Output is correct
28 Correct 5 ms 8296 KB Output is correct
29 Correct 5 ms 8180 KB Output is correct
30 Runtime error 387 ms 1048576 KB Execution killed with signal 9
31 Halted 0 ms 0 KB -