Submission #431564

#	Time	Username	Problem	Language	Result	Execution time	Memory
431564		rainboy	Ancient Books (IOI17_books)	C++98	50 / 100	181 ms	18772 KiB

books

#include "books.h"

using namespace std;

const int N = 1000000;

typedef vector<int> vi;

int dd[N];

long long minimum_walk(vi pp, int s) {
	int n = pp.size(), i;
	long long ans;

	ans = 0;
	for (i = 0; i < n; i++)
		if (i < pp[i])
			ans += pp[i] - i, dd[i]++, dd[pp[i]]--;
		else if (i > pp[i])
			ans += i - pp[i], dd[pp[i]]++, dd[i]--;
	for (i = 1; i < n - 1; i++)
		dd[i] += dd[i - 1];
	i = n - 1;
	while (i >= 0 && pp[i] == i)
		i--;
	for (i--; i >= 0; i--)
		if (dd[i] == 0)
			ans += 2;
	return ans;
}

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