Submission #1053004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053004		abczz	Ancient Books (IOI17_books)	C++17	50 / 100	64 ms	15184 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, x, y, 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;
	x = y = s;
	while (true) {
		if (x < n && x != p[x]) break;
		if (y >= 0 && y != p[y]) break;
		++x, --y;
		f += 2;
	}
	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