Submission #170839

#	Time	Username	Problem	Language	Result	Execution time	Memory
170839		Sorting	Ancient Books (IOI17_books)	C++14	100 / 100	295 ms	38860 KiB

books

#include <bits/stdc++.h>
#include "books.h"

using namespace std;

const long long inf = 1e18;

long long bfs(int from, 
             int to, 
             const int &n, 
             const vector<pair<int, int> > &range){
	vector<bool> used(n, false);
	vector<long long> dist(n);
	deque<int> q;

	for(int i = 0; i < n; ++i)
		dist[i] = inf;

	q.push_back(from);
	dist[from] = 0;

	int l = from, r = from;
	while(!q.empty()){
		int u = q.front();
		q.pop_front();

		if(u == to)
			return dist[to];
		if(used[u])
			continue;
		used[u] = true;
		r = max(r, u);
		l = min(l, u);
	
		if(range[u].first < l){
			for(int i = range[u].first; i < l; ++i){
				if(used[i])
					continue;

				q.push_front(i);
				dist[i] = dist[u];
			}
			l = range[u].first;
		}
		if(range[u].second > r){
			for(int i = r + 1; i <= range[u].second; ++i){
				if(used[i])
					continue;

				q.push_front(i);
				dist[i] = dist[u];
			}
			r = range[u].second;
		}

		if(u + 1 < n && dist[u + 1] > dist[u] + 1){
			dist[u + 1] = dist[u] + 1;
			q.push_back(u + 1);
		}
		if(range[u].first - 1 >= 0 && dist[u - 1] > dist[u] + 1){
			dist[u - 1] = dist[u] + 1;
			q.push_back(u - 1);
		}
	}

	return inf;
}

long long minimum_walk(vector<int> p, int s) {
	int n = (int)p.size();
	vector<int> rev(n);
	vector<pair<int, int> > range(n);
	long long ans = 0;

	for(int i = 0; i < n; ++i){
		rev[p[i]] = i;
		range[i] = {i, i};
	}

	int l = s, r = s;
	for(int i = 0; i < n; ++i){
		if(p[i] != i){
			l = min(l, i);
			r = max(r, i);
		}
	}

	for(int i = 0; i < n; ++i){
		if(p[i] != i){
			vector<int> cycle;

			int v = i;
			do{
				ans += abs(p[v] - v);
				cycle.push_back(v);

				int prev = v;
				v = p[v];
				p[prev] = prev;
			}
			while(v != i);

			int l_cycle = cycle[0], r_cycle = cycle[0];
			for(int x: cycle){
				l_cycle = min(l_cycle, x);
				r_cycle = max(r_cycle, x);
			}

			for(int x: cycle)
				range[x] = {l_cycle, r_cycle};
		}
	}

	long long l_ans = bfs(s, l, n, range);
	long long r_ans = bfs(s, r, n, range);

	ans += r_ans + l_ans + bfs(l, r, n, range);

	return ans;
}

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