제출 #431564

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
431564		rainboy	고대 책들 (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