Submission #605713

#	Time	Username	Problem	Language	Result	Execution time	Memory
605713		dnass	Ancient Books (IOI17_books)	C++17	50 / 100	308 ms	110644 KiB

books

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

lld n;

lld minimum_walk(vector<int> p, int s){
	n = (lld) p.size();
	lld ans = 0;
	for(lld i=0;i<n;i++) ans+=abs(p[i]-i);
	vector<bool> vis(n, false);
	vector<vector<lld>> cycles;
	vector<pair<lld,lld>> evs;
	for(lld i=0;i<n;i++){
		if(!vis[i]){
			vector<lld> tmp;
			lld x = i;
			while(true){
				if(vis[x]) break;
				tmp.push_back(x);
				vis[x] = true;
				x = p[x];
			}
			cycles.push_back(tmp);
			sort(tmp.begin(), tmp.end());
			evs.push_back({tmp[0], 0});
			evs.push_back({*tmp.rbegin(), 1});
		}
	}
	sort(evs.begin(), evs.end());
	lld op = 0;
	deque<pair<lld,lld>> blocks;
	lld beg = 0;
	for(lld i=0;i<(lld)evs.size();i++){
		if(evs[i].second==0){
			if(op==0) beg = evs[i].first;
			op++;
		}else{
			op--;
			if(op==0) blocks.push_back({beg,evs[i].first});
		}
	}
	while(!blocks.empty()&&blocks.back().first==blocks.back().second&&blocks.back().first>s) blocks.pop_back();
	while(!blocks.empty()&&blocks.front().first==blocks.front().second&&blocks.front().first<s) blocks.pop_front();
	for(lld i=1;i<(lld)blocks.size();i++){
		ans += 2*(blocks[i].first-blocks[i-1].second);
	}
	return ans;
}

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