Submission #581992

#	Time	Username	Problem	Language	Result	Execution time	Memory
581992		alireza_kaviani	Ancient Books (IOI17_books)	C++17	100 / 100	447 ms	52656 KiB

books

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

typedef long long ll;
typedef pair<int, int> pii;

#define sep			' '
#define X			first
#define Y			second
#define all(x)		(x).begin() , (x).end()
#define SZ(x)		int(x.size())

const int MAXN = 1e6 + 10;

ll n , s , sum , P[MAXN] , mark[MAXN] , L[MAXN] , R[MAXN] , ps[MAXN];

ll minimum_walk(vector<int> p, int S) {
	n = SZ(p); s = S;
	for(int i = 0 ; i < n ; i++){
		P[i] = p[i];
		sum += abs(P[i] - i);
	}
	int l = 0 , r = n - 1;
	while(r > l && r > s && P[r] == r)	r--;
	while(l <= r && l < s && P[l] == l)	l++;
	if(l == r && P[l] == P[r]){
		return 0;
	}
	for(int i = l ; i <= r ; i++){
		L[i] = R[i] = i;
	}
	for(int i = l ; i <= r ; i++){
		if(!mark[i]){
			vector<int> V;
			int x = i;
			while(!mark[x]){
				mark[x] = 1;
				V.push_back(x);
				x = P[x];
			}
			sort(all(V));
			for(int j = 0 ; j + 1 < SZ(V) ; j++){
				int v = V[j] , u = V[j + 1];
				R[v] = u; L[u] = v;
				ps[v]++; ps[u]--;
			}
		}
	}
	partial_sum(ps , ps + MAXN , ps);
	vector<int> comps;
	for(int i = l ; i <= r ; i++){
		if(ps[i] == 0){
			comps.push_back(i);
		}
	}

	int t = *lower_bound(all(comps) , s);
	int curl = s , curr = s;
	int mnl = L[s] , mxr = R[s];
	ll ans = sum + SZ(comps) * 2 - 2;
	while(1){
		while(mnl != curl || mxr != curr){
			if(mnl != curl){
				curl--;
				mnl = min((ll)mnl , L[curl]);
				mxr = max((ll)mxr , R[curl]);
			}
			else{
				curr++;
				mnl = min((ll)mnl , L[curr]);
				mxr = max((ll)mxr , R[curr]);
			}
		}
		if(curr >= t){
			break;
		}
		ans += 2;
		curl--;
		mnl = min((ll)mnl , L[curl]);
		mxr = max((ll)mxr , R[curl]);
		curr++;
		mnl = min((ll)mnl , L[curr]);
		mxr = max((ll)mxr , R[curr]);
	}

	return ans;
}

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