Submission #137629

#	Time	Username	Problem	Language	Result	Execution time	Memory
137629		random0029	고대 책들 (IOI17_books)	C++14	50 / 100	225 ms	18156 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);
	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);
		}
	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 (fail)
		vec.push_back({st, st});
	sort(vec.begin(), vec.end());
	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