Submission #1037578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037578		HappyCapybara	Ancient Books (IOI17_books)	C++17	50 / 100	85 ms	19028 KiB

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

ll minimum_walk(vector<int> p, int s){
	int n = p.size();
	ll d = 0;
	int nt = 0;
	for (int i=0; i<n; i++){
		if (p[i] != i) nt++;
		d += abs(p[i]-i);
	}
	ll e = 0;
	vector<int> q(n);
	for (int i=0; i<n; i++) q[p[i]] = i;
	int l = 0, r = 0, cur = 0;
	while (l < n){
		r = max(r, max(p[l], q[l]));
		if (p[l] != l) cur++;
		if (l == r && cur != nt) e++;
		l++;
	}
	return d + 2*e;
}

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