Submission #601014

#	Time	Username	Problem	Language	Result	Execution time	Memory
601014		Lucpp	고대 책들 (IOI17_books)	C++17	22 / 100	2045 ms	20448 KiB

books

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

long long minimum_walk(vector<int> p, int s){
	int n = (int)p.size();
	ll ans = 0;
	vector<int> cycle(n, -1);
	vector<int> cmi, cma;
	int numCycles = 0;
	for(int i = 0; i < n; i++){
		if(cycle[i] == -1 && p[i] != i){
			int mi = i, ma = i;
			int j = i;
			do
			{
				mi = min(mi, j);
				ma = max(ma, j);
				cycle[j] = numCycles;
				ans += abs(j-p[j]);
				j = p[j];
			}while(j != i);
			numCycles++;
			cmi.push_back(mi);
			cma.push_back(ma);
		}
	}
	int mi = s, ma = s;
	int l = s, r = s;
	vector<bool> vis(numCycles);
	while(true){
		int i = -1;
		while(r <= ma){
			if(cycle[r] != -1 && !vis[cycle[r]]){
				i = r;
				break;
			}
			else r++;
		}
		if(i == -1)
		while(l >= mi){
			if(cycle[l] != -1 && !vis[cycle[l]]){
				i = l;
				break;
			}
			else l--;
		}
		if(i == -1){
			int costL = 2*n, costR = 2*n;
			int candL = -1, candR = -1;
			for(int j = l; j >= 0; j--){
				if(cycle[j] != -1 && cma[cycle[j]] > ma){
					costL = 2*(l+1-j);
					candL = j;
					break;
				}
			}
			for(int j = r; j < n; j++){
				if(cycle[j] != -1 && cmi[cycle[j]] < mi){
					costR = 2*(j+1-r);
					candR = j;
					break;
				}
			}
			if(costL < costR) i = candL;
			else i = candR;
			if(i != -1) ans += min(costL, costR);
			if(i == -1){
				int oldR = r, oldL = l;
				while(r < n){
					if(cycle[r] != -1 && !vis[cycle[r]]){
						i = r;
						ans += 2*(r+1-oldR);
						break;
					}
					r++;
				}
				if(i == -1)
				while(l >= 0){
					if(cycle[l] != -1 && !vis[cycle[l]]){
						i = l;
						ans += 2*(oldL+1-l);
						break;
					}
					l--;
				}
			}
		}
		if(i == -1) break;
		vis[cycle[i]] = true;
		mi = min(mi, cmi[cycle[i]]);
		ma = max(ma, cma[cycle[i]]);
	}
	return ans;
}

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