Submission #1080509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080509		Elias	Ancient Books (IOI17_books)	C++17	50 / 100	128 ms	27216 KiB

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 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30