Submission #123074

#	Time	Username	Problem	Language	Result	Execution time	Memory
123074		SirCeness	Ancient Books (IOI17_books)	C++14	0 / 100	2 ms	376 KiB

books

#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define inside sl<=l&&r<=sr
#define outside r<sl||sr<l
#define inf 1000000009
using namespace std;
typedef long long ll;

int n;
vector<int> arr;
vector<ll> numara;
int num = 0;
vector<pair<ll, ll> > minler;


ll minimum_walk(vector<int> p, int s){
	arr = p;
	n = p.size();
	numara.resize(n);
	ll ans = 0;
	for (int i = 0; i < n; i++) numara[i] = -1;
	for (int i = 0; i < n; i++){
		if (numara[i] == -1 && p[i] != i){
			int node = i;
			int lmost = node;
			int rmost = node;
			while (numara[node] == -1){
				numara[node] = num;
				node = p[node];
				lmost = min(lmost, node);
				rmost = max(rmost, node);
			}
			num++;
			ans += (2*(rmost-lmost));
		}
	}
	
	//for (int i = 0; i < n; i++) cout << numara[i] << " "; cout << endl;
	
	//cout << "num: " << num << endl;
	minler.resize(num);
	for (int i = 0; i < num; i++) minler[i] = mp(inf, inf);
	for (int i = s; i < n; i++){
		if (numara[i] != -1 && minler[numara[i]].second == inf){
			minler[numara[i]].second = i-s;
		}
	}
	
	for (int i = s; i >= 0; i--){
		if (numara[i] != -1 && minler[numara[i]].first == inf){
			minler[numara[i]].first = s-i;
		}
	}
	
	
	minler.pb(mp(0, inf));
	minler.pb(mp(inf, 0));
	
	
	sort(minler.begin(), minler.end());
	
	ll best = inf;
	ll cmax = 0;
	for (int i = minler.size()-1; i > 0; i--){
		cmax = max(cmax, minler[i].second);
		best = min(best, cmax + minler[i-1].first);
	}
	
	//cout << "ans: " << ans <<endl;
	
	ans += best*2;
	return ans;
}

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