Submission #137714

#	Time	Username	Problem	Language	Result	Execution time	Memory
137714		random0029	Ancient Books (IOI17_books)	C++14	50 / 100	239 ms	20712 KiB

books

// ItnoE
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000006;
int n, M[N], A[N];
int64_t minimum_walk(vector < int > P, int st)
{
	n = (int)P.size();
	ll SM = 0;
	for (int i = 0; i < n; i ++)
		SM += abs(P[i] - i);
	vector < pair < int , int > > cyc;
	for (int i = 0; i < n; i ++)
		if (!M[i] && P[i] != i)
		{
			int v = i;
			int Mx = -N * 2, Mn = N * 2;
			while (!M[v])
			{
				M[v] = 1;
				Mn = min(Mn, v);
				Mx = max(Mx, v);
				v = P[v];
			}
			A[Mn] = max(A[Mn], Mx);
			cyc.push_back({Mn, Mx});
		}
	if (SM == 0)
		return (SM);
	//bool fail = 1;
	int Mx = 0, last = -1;
	vector < pair < int , int > > vec;
	for (int i = 0; i < n; i ++)
	{
		Mx = max({Mx, A[i], i});
		if (P[i] != i && last == -1)
			last = i;
		if (P[i] == i)
			continue;
		if (Mx == i)
			vec.push_back({last, Mx}), last = -1;
		//if (i <= st && st <= Mx)
			//fail = 0;
	}
	if (P[st] == st)
	{
		int le = st, ri = st;
		while (le >= 0 && P[le] == le)
			le --;
		while (ri < n && P[ri] == ri)
			ri ++;
		if (le == -1) le ++;
		if (ri == n) ri --;
		SM += (ri - le) * 2;
	}
	if (st != 0 && P[st] != st)
	{
		pair < int , int > X;
		for (auto Y : vec)
			if (Y.first <= st && st <= Y.second)
				X = Y;
		SM += max(st - X.first, X.second - st);
	}
	for (int i = 1; i < (int)vec.size(); i ++)
	{
		SM += (vec[i].first - vec[i - 1].second) * 2;
		assert(vec[i].first > vec[i - 1].second);
	}
	return (SM);
}

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