Submission #838201

#	Time	Username	Problem	Language	Result	Execution time	Memory
838201		Johann	Ancient Books (IOI17_books)	C++14	50 / 100	161 ms	34772 KiB

books

#include "books.h"
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N;
ll cost;
vi vis, P;

void cycle(int i, int &mini, int &maxi)
{
	if (vis[i])
		return;
	mini = min(mini, i);
	maxi = max(maxi, i);
	vis[i] = 1;
	cost += (ll)abs(P[i] - i);
	cycle(P[i], mini, maxi);
}

long long minimum_walk(std::vector<int> p, int s)
{
	N = sz(p);
	P.resize(N);
	for (int i = 0; i < N; ++i)
		P[i] = p[i];

	vis.assign(N, false);
	cost = 0;
	vpii borders;
	for (int i = 0, mini, maxi; i < N; ++i)
	{
		if (!vis[i] && P[i] != i)
		{
			mini = maxi = i;
			cycle(i, mini, maxi);
			borders.push_back({mini, maxi});
		}
	}
	sort(all(borders));

	ll pos = s;
	for (pii b : borders)
	{
		cost += 2 * max(0LL, b.first - pos);
		pos = max(pos, b.second);
	}

	return cost;
}

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30