Submission #921041

#	Time	Username	Problem	Language	Result	Execution time	Memory
921041		siewjh	Ancient Books (IOI17_books)	C++17	50 / 100	126 ms	29244 KiB

books

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

ll minimum_walk(vector<int> p, int s) {
	int nums = p.size();
	vector<int> cyc(nums, -1);
	ll ans = 0;
	int mn = s, mx = s;
	vector<pair<int, int>> ranges;
	for (int i = 0; i < nums; i++)
		if (cyc[i] == -1){
			int curr = i, cmn = i, cmx = i;
			do{
				ans += abs(curr - p[curr]);
				cyc[curr] = i;
				cmn = min(cmn, curr);
				cmx = max(cmx, curr);
				curr = p[curr];
			} while (curr != i);
			ranges.push_back({cmn, cmx});
			if (p[i] != i){
				mn = min(mn, cmn);
				mx = max(mx, cmx);
			}
		}
	sort(ranges.begin(), ranges.end());
	int cmx = -1;
	ll cnt = 0;
	for (auto &[l, r] : ranges){
		if (l < mn) continue;
		if (l > mx) break;
		if (l > cmx) cnt++;
		cmx = max(cmx, r);
	}
	return ans + (cnt - 1) * 2;
}

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