Submission #1181536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181536		HappyCapybara	Ancient Books (IOI17_books)	C++17	0 / 100	0 ms	328 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 res = 0;
	vector<pair<int,int>> cc;
	vector<bool> seen(n, false);
	int lm = -1;
	for (int i=0; i<n; i++){
		if (p[i] != i) lm = i;
		if (seen[i]) continue;
		seen[i] = true;
		if (p[i] == i) continue;
		int l = i, r = i;
		res += abs(p[i]-i);
		int cur = p[i];
		seen[cur] = true;
		while (cur != i){
			res += abs(p[cur]-cur);
			cur = p[cur];
			seen[cur] = true;
			l = min(l, cur);
			r = max(r, cur);
		}
		cc.push_back({l, r});
	}
	//cout << res << endl;
	sort(cc.begin(), cc.end());
	//for (auto [l, r] : cc) cout << l << " " << r << endl;
	int cur = -1, rb = 0;
	//cout << lm << endl;
	for (int i=0; i<lm; i++){
		while (cur+1 < cc.size() && cc[cur+1].first <= i){
			cur++;
			rb = max(rb, cc[cur].second);
		}
		if (rb <= i) res += 2;
	}
	return res;
}

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