Submission #601098

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
601098	2022-07-21T11:08:40 Z	DanShaders	Ancient Books (IOI17_books)	C++17	42 / 100	92 ms	16304 KB

books

//Cgrader.cpp
#include "books.h"
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
using ll = long long;
using ld = long double;

const int N = 1e3 + 10, INF = 0x3f3f3f3f;

int cc[N], cnt[N], clef[N], crig[N];
pair<int, int> q[N][N];
int dp[N][N];

ll minimum_walk(vector<int> p, int s) {
	int rl = 0, rr = sz(p);
	while (rl < s) {
		if (p[rl] == rl) {
			++rl;
		} else {
			break;
		}
	}
	while (rr > s + 1) {
		if (p[rr - 1] == rr - 1) {
			--rr;
		} else {
			break;
		}
	}
	p = vector(begin(p) + rl, begin(p) + rr);
	s -= rl;
	for (int &u : p) {
		u -= rl;
	}

	int n = sz(p), m = 0;
	ll ans = 0;
	fill(all(cc), -1);
	for (int i = 0; i < n; ++i) {
		ans += abs(p[i] - i);
		if (cc[i] == -1) {
			clef[m] = crig[m] = i;
			int j = i;
			while (cc[j] == -1) {
				cc[j] = m;
				cnt[m]++;
				crig[m] = max(crig[m], j);
				j = p[j];
			}
			++m;
		}
	}
	for (int i = 0; i < n; ++i) {
		q[i][i] = {clef[cc[i]], crig[cc[i]]};
		for (int j = i + 1; j < n; ++j) {
			q[i][j].x = min(q[i][j - 1].x, clef[cc[j]]);
			q[i][j].y = max(q[i][j - 1].y, crig[cc[j]]);
		}
	}
	for (int len = n - 1; len > 0; --len) {
		for (int i = 0; i <= n - len; ++i) {
			int j = i + len - 1;
			if (q[i][j] != pair{i, j}) {
				// cout << "at " << i << " " << j << ", extending to " << q[i][j].x << " " << q[i][j].y << endl;
				dp[i][j] = dp[q[i][j].x][q[i][j].y];
			} else {
				dp[i][j] = +INF;
				if (i) {
					dp[i][j] = dp[i - 1][j] + 2;
				}
				if (j != n - 1) {
					dp[i][j] = min(dp[i][j], dp[i][j + 1] + 2);
				}
			}

		}
	}
	return ans + dp[s][s];
}

Subtask #1
12.0 / 12.0

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

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	11 ms	11200 KB	Output is correct
20	Correct	10 ms	11188 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	12 ms	11220 KB	Output is correct
23	Correct	13 ms	11092 KB	Output is correct
24	Correct	12 ms	11220 KB	Output is correct
25	Correct	13 ms	11220 KB	Output is correct
26	Correct	11 ms	11160 KB	Output is correct
27	Correct	11 ms	11220 KB	Output is correct
28	Correct	13 ms	11188 KB	Output is correct
29	Correct	11 ms	11220 KB	Output is correct

Subtask #3
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	11 ms	11200 KB	Output is correct
20	Correct	10 ms	11188 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	12 ms	11220 KB	Output is correct
23	Correct	13 ms	11092 KB	Output is correct
24	Correct	12 ms	11220 KB	Output is correct
25	Correct	13 ms	11220 KB	Output is correct
26	Correct	11 ms	11160 KB	Output is correct
27	Correct	11 ms	11220 KB	Output is correct
28	Correct	13 ms	11188 KB	Output is correct
29	Correct	11 ms	11220 KB	Output is correct
30	Runtime error	92 ms	16304 KB	Execution killed with signal 11
31	Halted	0 ms	0 KB	-

Subtask #4
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	11156 KB	Output is correct
2	Correct	12 ms	11196 KB	Output is correct
3	Correct	13 ms	11124 KB	Output is correct
4	Correct	16 ms	11092 KB	Output is correct
5	Correct	13 ms	11180 KB	Output is correct
6	Correct	11 ms	11104 KB	Output is correct
7	Correct	11 ms	11140 KB	Output is correct
8	Correct	11 ms	11208 KB	Output is correct
9	Correct	11 ms	11220 KB	Output is correct
10	Correct	1 ms	308 KB	Output is correct
11	Correct	11 ms	11220 KB	Output is correct
12	Correct	11 ms	11220 KB	Output is correct
13	Correct	11 ms	11220 KB	Output is correct
14	Correct	16 ms	11124 KB	Output is correct
15	Correct	11 ms	11220 KB	Output is correct
16	Correct	11 ms	11220 KB	Output is correct
17	Correct	10 ms	11196 KB	Output is correct
18	Correct	11 ms	11220 KB	Output is correct
19	Correct	11 ms	11192 KB	Output is correct
20	Correct	11 ms	11220 KB	Output is correct

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	11 ms	11200 KB	Output is correct
20	Correct	10 ms	11188 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	12 ms	11220 KB	Output is correct
23	Correct	13 ms	11092 KB	Output is correct
24	Correct	12 ms	11220 KB	Output is correct
25	Correct	13 ms	11220 KB	Output is correct
26	Correct	11 ms	11160 KB	Output is correct
27	Correct	11 ms	11220 KB	Output is correct
28	Correct	13 ms	11188 KB	Output is correct
29	Correct	11 ms	11220 KB	Output is correct
30	Runtime error	92 ms	16304 KB	Execution killed with signal 11
31	Halted	0 ms	0 KB	-

Submission #601098

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 28.0

Subtask #4 20.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
20.0 / 20.0

Subtask #5
0 / 30.0