Submission #507644

#	Time	Username	Problem	Language	Result	Execution time	Memory
507644		Hanksburger	Ancient Books (IOI17_books)	C++17	50 / 100	116 ms	30564 KiB

books

#include <bits/stdc++.h>
using namespace std;
long long pos[1000005], num[1000005];
long long minimum_walk(vector<int> p, int s)
{
	long long n=p.size(), l=-1, r=-1, ans=0;
	for (long long i=0; i<n; i++)
		pos[p[i]]=i;
	for (long long i=0; i<n; i++)
	{
		if (i<=pos[i])
		{
			ans+=pos[i]-i;
			num[i]++;
			num[pos[i]]--;
		}
		else
		{
			ans+=i-pos[i];
			num[pos[i]]++;
			num[i]--;
		}
	}
	for (long long i=1; i<=n-2; i++)
		num[i]+=num[i-1];
	for (long long i=0; i<=n-2; i++)
	{
		if (num[i])
		{
			l=i;
			break;
		}
	}
	for (long long i=n-2; i>=0; i--)
	{
		if (num[i])
		{
			r=i;
			break;
		}
	}
	if (l!=-1)
	{
		for (long long i=l; i<=r; i++)
			if (!num[i])
				ans+=2;
		if (s<l)
			ans+=(l-s)*2;
		if (s>=r+2)
			ans+=(s-r-1)*2;
	}
	return ans;
}

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