Submission #601097

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
601097	2022-07-21T11:07:09 Z	DanShaders	Ancient Books (IOI17_books)	C++17	22 / 100	97 ms	17604 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];
				}
				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	308 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	316 KB	Output is correct
5	Correct	1 ms	312 KB	Output is correct
6	Correct	1 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	0 ms	340 KB	Output is correct
10	Correct	0 ms	312 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	308 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	312 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	316 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	308 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	316 KB	Output is correct
5	Correct	1 ms	312 KB	Output is correct
6	Correct	1 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	0 ms	340 KB	Output is correct
10	Correct	0 ms	312 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	308 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	312 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	316 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	12 ms	11220 KB	Output is correct
20	Correct	12 ms	11220 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	13 ms	11200 KB	Output is correct
23	Correct	16 ms	11196 KB	Output is correct
24	Correct	12 ms	11208 KB	Output is correct
25	Correct	12 ms	11188 KB	Output is correct
26	Correct	11 ms	11220 KB	Output is correct
27	Correct	12 ms	11220 KB	Output is correct
28	Correct	11 ms	11104 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	308 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	316 KB	Output is correct
5	Correct	1 ms	312 KB	Output is correct
6	Correct	1 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	0 ms	340 KB	Output is correct
10	Correct	0 ms	312 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	308 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	312 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	316 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	12 ms	11220 KB	Output is correct
20	Correct	12 ms	11220 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	13 ms	11200 KB	Output is correct
23	Correct	16 ms	11196 KB	Output is correct
24	Correct	12 ms	11208 KB	Output is correct
25	Correct	12 ms	11188 KB	Output is correct
26	Correct	11 ms	11220 KB	Output is correct
27	Correct	12 ms	11220 KB	Output is correct
28	Correct	11 ms	11104 KB	Output is correct
29	Correct	11 ms	11220 KB	Output is correct
30	Runtime error	97 ms	17604 KB	Execution killed with signal 11
31	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	12 ms	11220 KB	3rd lines differ - on the 1st token, expected: '3304', found: '2744'
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	308 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	316 KB	Output is correct
5	Correct	1 ms	312 KB	Output is correct
6	Correct	1 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	0 ms	340 KB	Output is correct
10	Correct	0 ms	312 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	308 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	312 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	316 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	12 ms	11220 KB	Output is correct
20	Correct	12 ms	11220 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	13 ms	11200 KB	Output is correct
23	Correct	16 ms	11196 KB	Output is correct
24	Correct	12 ms	11208 KB	Output is correct
25	Correct	12 ms	11188 KB	Output is correct
26	Correct	11 ms	11220 KB	Output is correct
27	Correct	12 ms	11220 KB	Output is correct
28	Correct	11 ms	11104 KB	Output is correct
29	Correct	11 ms	11220 KB	Output is correct
30	Runtime error	97 ms	17604 KB	Execution killed with signal 11
31	Halted	0 ms	0 KB	-

Submission #601097

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