Submission #1052989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052989		abczz	Ancient Books (IOI17_books)	C++17	50 / 100	58 ms	15188 KiB

books

#include "books.h"
#include <iostream>
#define ll long long

using namespace std;

long long minimum_walk(std::vector<int> p, int s) {
	ll n = p.size(), l, r, f = 0, mx = 0;
	for (int i=0; i<n; ++i) {
		f += abs(i-p[i]);
	}
	l = n, r = -1;
	for (int i=0; i<n; ++i) {
		if (p[i] != i) {
			l = i;
			break;
		}
	}
	for (int i=n-1; i>=0; --i) {
		if (p[i] != i) {
			r = i;
			break;
		}
	}
	if (l == n) return 0;
	if (s < l) f += 2*(l-s);
	else if (r < s) f += 2*(s-r);
	for (int i=l; i<=r; ++i) {
		mx = max(mx, (ll)p[i]);
		if (mx == i) f += 2;
	}
	f -= 2;
	return f;
}

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