Submission #1080509

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1080509	2024-08-29T10:36:50 Z	Elias	Ancient Books (IOI17_books)	C++17	50 / 100	128 ms	27216 KB

books

#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif

#include <bits/stdc++.h>

using namespace std;

#ifdef _DEBUG
long long minimum_walk(std::vector<int> p, int s);
#else
#include "books.h"
#endif

int n;

#define ll long long

struct Group
{
	int l = 10000000, r = -1;
};

bool operator<(Group a, Group b) {
	return a.l < b.l;
}

long long minimum_walk(std::vector<int> p, int s)
{
	n = p.size();
	vector<int> visited(p.size());

	vector<Group> groups;

	ll cost = 0;
	for (int i = 0; i < n; i++)
	{
		int index = i;
		if (visited[i])
			continue;

		Group group;

		do
		{
			visited[index] = 1;
			group.l = min(group.l, index);
			group.r = max(group.r, index);

			int new_index = p[index];
			cost += abs<ll>(index - new_index);
			index = new_index;
		} while (index != i);

		groups.push_back(group);
	}

	while (groups.size() && groups.back().l == groups.back().r)
		groups.pop_back();

	sort(groups.begin(), groups.end());

	int ending = 0;

	ll extra_cost = 0;

	for (auto [l, r] : groups) {
		if (l <= ending) {
			ending = max(ending, r);
		} else {
			extra_cost += 2;
			ending = max(ending, r);
		}
	}

	return cost + extra_cost;
}

#ifdef _DEBUG

using namespace std;

int main()
{
	int n, s;
	assert(2 == scanf("%d %d", &n, &s));

	vector<int> p((unsigned)n);
	for (int i = 0; i < n; i++)
		assert(1 == scanf("%d", &p[(unsigned)i]));

	long long res = minimum_walk(p, s);
	printf("%lld\n", res);
	return 0;
}

#endif

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	344 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	1 ms	356 KB	Output is correct
12	Correct	0 ms	344 KB	Output is correct
13	Correct	1 ms	356 KB	Output is correct
14	Correct	0 ms	352 KB	Output is correct
15	Correct	1 ms	352 KB	Output is correct
16	Correct	0 ms	352 KB	Output is correct
17	Correct	0 ms	436 KB	Output is correct
18	Correct	0 ms	352 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	344 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	1 ms	356 KB	Output is correct
12	Correct	0 ms	344 KB	Output is correct
13	Correct	1 ms	356 KB	Output is correct
14	Correct	0 ms	352 KB	Output is correct
15	Correct	1 ms	352 KB	Output is correct
16	Correct	0 ms	352 KB	Output is correct
17	Correct	0 ms	436 KB	Output is correct
18	Correct	0 ms	352 KB	Output is correct
19	Correct	1 ms	352 KB	Output is correct
20	Correct	0 ms	356 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	1 ms	348 KB	Output is correct
28	Correct	1 ms	348 KB	Output is correct
29	Correct	1 ms	348 KB	Output is correct

Subtask #3
28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	344 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	1 ms	356 KB	Output is correct
12	Correct	0 ms	344 KB	Output is correct
13	Correct	1 ms	356 KB	Output is correct
14	Correct	0 ms	352 KB	Output is correct
15	Correct	1 ms	352 KB	Output is correct
16	Correct	0 ms	352 KB	Output is correct
17	Correct	0 ms	436 KB	Output is correct
18	Correct	0 ms	352 KB	Output is correct
19	Correct	1 ms	352 KB	Output is correct
20	Correct	0 ms	356 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	1 ms	348 KB	Output is correct
28	Correct	1 ms	348 KB	Output is correct
29	Correct	1 ms	348 KB	Output is correct
30	Correct	118 ms	18888 KB	Output is correct
31	Correct	128 ms	18768 KB	Output is correct
32	Correct	98 ms	27080 KB	Output is correct
33	Correct	96 ms	27068 KB	Output is correct
34	Correct	93 ms	27216 KB	Output is correct
35	Correct	95 ms	27100 KB	Output is correct
36	Correct	84 ms	20908 KB	Output is correct
37	Correct	89 ms	19416 KB	Output is correct
38	Correct	101 ms	18912 KB	Output is correct
39	Correct	120 ms	18796 KB	Output is correct
40	Correct	93 ms	18792 KB	Output is correct
41	Correct	118 ms	18768 KB	Output is correct
42	Correct	105 ms	18652 KB	Output is correct
43	Correct	105 ms	27048 KB	Output is correct

Subtask #4
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	348 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	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	344 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	1 ms	356 KB	Output is correct
12	Correct	0 ms	344 KB	Output is correct
13	Correct	1 ms	356 KB	Output is correct
14	Correct	0 ms	352 KB	Output is correct
15	Correct	1 ms	352 KB	Output is correct
16	Correct	0 ms	352 KB	Output is correct
17	Correct	0 ms	436 KB	Output is correct
18	Correct	0 ms	352 KB	Output is correct
19	Correct	1 ms	352 KB	Output is correct
20	Correct	0 ms	356 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	1 ms	348 KB	Output is correct
28	Correct	1 ms	348 KB	Output is correct
29	Correct	1 ms	348 KB	Output is correct
30	Correct	118 ms	18888 KB	Output is correct
31	Correct	128 ms	18768 KB	Output is correct
32	Correct	98 ms	27080 KB	Output is correct
33	Correct	96 ms	27068 KB	Output is correct
34	Correct	93 ms	27216 KB	Output is correct
35	Correct	95 ms	27100 KB	Output is correct
36	Correct	84 ms	20908 KB	Output is correct
37	Correct	89 ms	19416 KB	Output is correct
38	Correct	101 ms	18912 KB	Output is correct
39	Correct	120 ms	18796 KB	Output is correct
40	Correct	93 ms	18792 KB	Output is correct
41	Correct	118 ms	18768 KB	Output is correct
42	Correct	105 ms	18652 KB	Output is correct
43	Correct	105 ms	27048 KB	Output is correct
44	Incorrect	0 ms	348 KB	3rd lines differ - on the 1st token, expected: '3304', found: '2744'
45	Halted	0 ms	0 KB	-

Submission #1080509

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 10.0 / 10.0

Subtask #3 28.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
28.0 / 28.0

Subtask #4
0 / 20.0

Subtask #5
0 / 30.0