Submission #526863

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526863	2022-02-16T12:02:26 Z	KoD	Ancient Books (IOI17_books)	C++17	22 / 100	101 ms	22996 KB

books

#include <bits/stdc++.h>
#include "books.h"

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using ll = long long;

ll minimum_walk(vector<int> P, int src) {
	{
		int l = 0;
		while (l < src and P[l] == l) {
			l += 1;
		}
		int r = (int)P.size() - 1;
		while (r > src and P[r] == r) {
			r -= 1;
		}
		src -= l;
		P.erase(P.begin() + r + 1, P.end());
		P.erase(P.begin(), P.begin() + l);
	}
	const int N = P.size();
	assert(N <= 1000);
	vector<int> min(N), max(N);
	vector<char> done(N);
	ll ret = 0;
	for (int i = 0; i < N; ++i) {
		if (!done[i]) {
			vector<int> list;
			for (int j = i; !done[j]; j = P[j]) {
				list.push_back(j);
				ret += std::abs(P[j] - j);
				done[j] = true;
			}
			const int l = *std::min_element(list.begin(), list.end());
			const int r = *std::max_element(list.begin(), list.end());
			for (const int j : list) {
				min[j] = l;
				max[j] = r;
			}
		}
	}
	vector dist(N, vector(N, N + 1));
	std::deque<pair<int, int>> que;
	const auto push0 = [&](const int l, const int r, const int d) {
		if (dist[l][r] > d) {
			dist[l][r] = d;
			que.emplace_front(l, r);
		}
	};
	const auto push1 = [&](const int l, const int r, const int d) {
		if (dist[l][r] > d + 1) {
			dist[l][r] = d + 1;
			que.emplace_back(l, r);
		}
	};
	push0(src, src, 0);
	while (!que.empty()) {
		const auto [l, r] = que.front();
		que.pop_front();
		push0(std::min({l, min[l], min[r]}), std::max({r, max[l], max[r]}), dist[l][r]);
		if (l < r) {
			push0(l + 1, r, dist[l][r]);
			push0(l, r - 1, dist[l][r]);
		}
		if (l > 0) {
			push1(l - 1, r, dist[l][r]);
		}
		if (r + 1 < N) {
			push1(l, r + 1, dist[l][r]);
		}
	}
	return ret + 2 * dist[0][N - 1];
}

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	220 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	0 ms	296 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	288 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	0 ms	288 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	292 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	0 ms	204 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	220 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	0 ms	296 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	288 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	0 ms	288 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	292 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	0 ms	204 KB	Output is correct
19	Correct	23 ms	8196 KB	Output is correct
20	Correct	30 ms	8408 KB	Output is correct
21	Correct	1 ms	292 KB	Output is correct
22	Correct	14 ms	4276 KB	Output is correct
23	Correct	15 ms	4256 KB	Output is correct
24	Correct	15 ms	4264 KB	Output is correct
25	Correct	17 ms	4300 KB	Output is correct
26	Correct	18 ms	4556 KB	Output is correct
27	Correct	19 ms	5072 KB	Output is correct
28	Correct	19 ms	5324 KB	Output is correct
29	Correct	20 ms	7020 KB	Output is correct

Subtask #3
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	220 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	0 ms	296 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	288 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	0 ms	288 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	292 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	0 ms	204 KB	Output is correct
19	Correct	23 ms	8196 KB	Output is correct
20	Correct	30 ms	8408 KB	Output is correct
21	Correct	1 ms	292 KB	Output is correct
22	Correct	14 ms	4276 KB	Output is correct
23	Correct	15 ms	4256 KB	Output is correct
24	Correct	15 ms	4264 KB	Output is correct
25	Correct	17 ms	4300 KB	Output is correct
26	Correct	18 ms	4556 KB	Output is correct
27	Correct	19 ms	5072 KB	Output is correct
28	Correct	19 ms	5324 KB	Output is correct
29	Correct	20 ms	7020 KB	Output is correct
30	Runtime error	101 ms	22996 KB	Execution killed with signal 6
31	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	5928 KB	Output is correct
2	Correct	20 ms	7248 KB	Output is correct
3	Correct	20 ms	6072 KB	Output is correct
4	Correct	15 ms	4136 KB	Output is correct
5	Correct	14 ms	4260 KB	Output is correct
6	Correct	21 ms	7076 KB	Output is correct
7	Correct	19 ms	6932 KB	Output is correct
8	Correct	18 ms	5352 KB	Output is correct
9	Correct	18 ms	5584 KB	Output is correct
10	Incorrect	1 ms	208 KB	3rd lines differ - on the 1st token, expected: '0', found: '999'
11	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	220 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	0 ms	296 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	288 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	0 ms	288 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	292 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	0 ms	204 KB	Output is correct
19	Correct	23 ms	8196 KB	Output is correct
20	Correct	30 ms	8408 KB	Output is correct
21	Correct	1 ms	292 KB	Output is correct
22	Correct	14 ms	4276 KB	Output is correct
23	Correct	15 ms	4256 KB	Output is correct
24	Correct	15 ms	4264 KB	Output is correct
25	Correct	17 ms	4300 KB	Output is correct
26	Correct	18 ms	4556 KB	Output is correct
27	Correct	19 ms	5072 KB	Output is correct
28	Correct	19 ms	5324 KB	Output is correct
29	Correct	20 ms	7020 KB	Output is correct
30	Runtime error	101 ms	22996 KB	Execution killed with signal 6
31	Halted	0 ms	0 KB	-

Submission #526863

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 28.0

Subtask #4 0 / 20.0

Subtask #5 0 / 30.0

Subtask #1
12.0 / 12.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 28.0

Subtask #4
0 / 20.0

Subtask #5
0 / 30.0