Submission #69353

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
69353	2018-08-20T15:21:54 Z	Bruteforceman	Ancient Books (IOI17_books)	C++11	12 / 100	68 ms	10556 KB

books

#include "books.h"
#include "bits/stdc++.h"
using namespace std;
int col[1000010];
bool vis[1000010];

bool v[1000010];
int l[1000010], r[1000010];
int cmp[1000010];

void dfs(int x, int c) {
	v[x] = true;
	for(int i = l[x]; i <= r[x]; i++) {
		cmp[i] = c;
		if(col[i] != -1 && v[col[i]] == false) {
			dfs(col[i], c);
		}
	}
}


long long minimum_walk(std::vector<int> p, int s) {
	long long ans = 0;
	int n = p.size();
	for(int i = 0; i < n-1; i++) {
		int go_left = 0;
		int go_right = 0;
		for(int j = 0; j <= i; j++) {
			if(p[j] > i) {
				++go_left;
			}
		}
		for(int j = i + 1; j < n; j++) {
			if(p[j] < i+1) {
				++go_right;
			}
		}
		assert(go_left == go_right);
		ans += go_left + go_right;
	}
	memset(col, -1, sizeof col);
	memset(v, false, sizeof v);

	int id = 0;
	for(int i = 0; i < n; i++) {
		if(col[i] != -1 || p[i] == i) continue;
		int cur = i;
		++id;
		l[id] = n;
		r[id] = 0; 
		while(col[cur] == -1) {
			l[id] = min(l[id], cur);
			r[id] = max(r[id], cur);
			col[cur] = id;
			cur = p[cur];
		}
	}
	memset(cmp, -1, sizeof cmp);
	int c = 0;
	for(int i = 1; i <= id; i++) {
		if(v[i] == false) {
			dfs(i, ++c);
		}	
	}
	id = c;
	for(int i = 0; i < n; i++) {
		col[i] = cmp[i];
	}
	int opt = 1e9;
	for(int i = s; i < n; i++) {
		memset(vis, false, sizeof vis);
		int cnt = 0;
		int add = abs(s - i);
		for(int j = s; j <= i; j++) {
			if(col[j] != -1) {
				if(vis[col[j]] == false) ++cnt;
				vis[col[j]] = true;
			}
		} 
		for(int j = s; j >= 0; j--) {
			if(col[j] != -1) {
				if(vis[col[j]] == false) ++cnt;
				vis[col[j]] = true;
			}	
			if(cnt == id) {
				add += abs(s - j);
				break;
			}
		}
		if(cnt == id) {
			opt = min(opt, 2 * add);
		}
	}
	ans += opt;
	return ans;
}

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	10104 KB	Output is correct
2	Correct	10 ms	10104 KB	Output is correct
3	Correct	11 ms	10136 KB	Output is correct
4	Correct	10 ms	10188 KB	Output is correct
5	Correct	10 ms	10188 KB	Output is correct
6	Correct	9 ms	10192 KB	Output is correct
7	Correct	10 ms	10192 KB	Output is correct
8	Correct	10 ms	10192 KB	Output is correct
9	Correct	11 ms	10196 KB	Output is correct
10	Correct	10 ms	10268 KB	Output is correct
11	Correct	10 ms	10268 KB	Output is correct
12	Correct	10 ms	10268 KB	Output is correct
13	Correct	11 ms	10268 KB	Output is correct
14	Correct	10 ms	10268 KB	Output is correct
15	Correct	10 ms	10272 KB	Output is correct
16	Correct	12 ms	10276 KB	Output is correct
17	Correct	11 ms	10288 KB	Output is correct
18	Correct	11 ms	10420 KB	Output is correct

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	10104 KB	Output is correct
2	Correct	10 ms	10104 KB	Output is correct
3	Correct	11 ms	10136 KB	Output is correct
4	Correct	10 ms	10188 KB	Output is correct
5	Correct	10 ms	10188 KB	Output is correct
6	Correct	9 ms	10192 KB	Output is correct
7	Correct	10 ms	10192 KB	Output is correct
8	Correct	10 ms	10192 KB	Output is correct
9	Correct	11 ms	10196 KB	Output is correct
10	Correct	10 ms	10268 KB	Output is correct
11	Correct	10 ms	10268 KB	Output is correct
12	Correct	10 ms	10268 KB	Output is correct
13	Correct	11 ms	10268 KB	Output is correct
14	Correct	10 ms	10268 KB	Output is correct
15	Correct	10 ms	10272 KB	Output is correct
16	Correct	12 ms	10276 KB	Output is correct
17	Correct	11 ms	10288 KB	Output is correct
18	Correct	11 ms	10420 KB	Output is correct
19	Correct	60 ms	10420 KB	Output is correct
20	Correct	67 ms	10556 KB	Output is correct
21	Correct	64 ms	10556 KB	Output is correct
22	Incorrect	68 ms	10556 KB	3rd lines differ - on the 1st token, expected: '2082', found: '2782'
23	Halted	0 ms	0 KB	-

Subtask #3
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	10104 KB	Output is correct
2	Correct	10 ms	10104 KB	Output is correct
3	Correct	11 ms	10136 KB	Output is correct
4	Correct	10 ms	10188 KB	Output is correct
5	Correct	10 ms	10188 KB	Output is correct
6	Correct	9 ms	10192 KB	Output is correct
7	Correct	10 ms	10192 KB	Output is correct
8	Correct	10 ms	10192 KB	Output is correct
9	Correct	11 ms	10196 KB	Output is correct
10	Correct	10 ms	10268 KB	Output is correct
11	Correct	10 ms	10268 KB	Output is correct
12	Correct	10 ms	10268 KB	Output is correct
13	Correct	11 ms	10268 KB	Output is correct
14	Correct	10 ms	10268 KB	Output is correct
15	Correct	10 ms	10272 KB	Output is correct
16	Correct	12 ms	10276 KB	Output is correct
17	Correct	11 ms	10288 KB	Output is correct
18	Correct	11 ms	10420 KB	Output is correct
19	Correct	60 ms	10420 KB	Output is correct
20	Correct	67 ms	10556 KB	Output is correct
21	Correct	64 ms	10556 KB	Output is correct
22	Incorrect	68 ms	10556 KB	3rd lines differ - on the 1st token, expected: '2082', found: '2782'
23	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	41 ms	10556 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	10 ms	10104 KB	Output is correct
2	Correct	10 ms	10104 KB	Output is correct
3	Correct	11 ms	10136 KB	Output is correct
4	Correct	10 ms	10188 KB	Output is correct
5	Correct	10 ms	10188 KB	Output is correct
6	Correct	9 ms	10192 KB	Output is correct
7	Correct	10 ms	10192 KB	Output is correct
8	Correct	10 ms	10192 KB	Output is correct
9	Correct	11 ms	10196 KB	Output is correct
10	Correct	10 ms	10268 KB	Output is correct
11	Correct	10 ms	10268 KB	Output is correct
12	Correct	10 ms	10268 KB	Output is correct
13	Correct	11 ms	10268 KB	Output is correct
14	Correct	10 ms	10268 KB	Output is correct
15	Correct	10 ms	10272 KB	Output is correct
16	Correct	12 ms	10276 KB	Output is correct
17	Correct	11 ms	10288 KB	Output is correct
18	Correct	11 ms	10420 KB	Output is correct
19	Correct	60 ms	10420 KB	Output is correct
20	Correct	67 ms	10556 KB	Output is correct
21	Correct	64 ms	10556 KB	Output is correct
22	Incorrect	68 ms	10556 KB	3rd lines differ - on the 1st token, expected: '2082', found: '2782'
23	Halted	0 ms	0 KB	-

Submission #69353

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 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
0 / 10.0

Subtask #3
0 / 28.0

Subtask #4
0 / 20.0

Subtask #5
0 / 30.0