제출 #125152

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
125152		Sorting	고대 책들 (IOI17_books)	C++14	50 / 100	258 ms	46856 KiB

books

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1e6 + 7;
 
bool used[N];
int a[N];
vector<int> v;
 
void dfs(int u){
	v.push_back(u);
	used[u] = true;
 
	if(!used[a[u]]){
		dfs(a[u]); 
	}
}
 
struct point{
	int x, y, idx;
 
	point();
	point(int x, int y, int idx){
		this->x = x;
		this->y = y;
		this->idx = idx;
	}
};
 
bool between(int x1, int y1, int x2, int y2){
	if(x1 > y1){
		swap(x1, y1);
	}
	if(x2 > y2){
		swap(x2, y2);
	}
 
	if(x2 < x1 && y1 < y2){
		return true;
	}
 
	return false;
}
 
vector<point> two1, two2;
int t, par[N];
bool poss[N];
 
long long minimum_walk(vector<int> p, int s){
	int n = (int)p.size();
	long long ans = 0;
 
	for(int i = 0; i < n; i++){
		used[i] = false;
		a[i] = p[i];
		par[i] = -1;
	}

	t = 0;
 
	for(int i = 0; i < n; i++){
		if(!used[i]){
			v.clear();
			dfs(i);
 
			poss[i] = true;
			for(int x: v){
				par[x] = t;
			}
			t++;
 
			int mn = n, mx = 0;
 
			for(int j = 0; j < (int)v.size() - 1; j++){
				ans += abs(v[j] - v[j + 1]);
				//two2.push_back(point(v[j], v[j + 1], -1));
			}
			if(v.size() != 1){
				ans += abs(v[0] - v.back());
				//two2.push_back(point(v[0], v.back(), -1));
			}
 
			for(int x: v){
				mn = min(mn, x);
				mx = max(mx, x);
			}
 
			while(mn != i);
 
			two1.push_back(point(mn, mx, i));
		}
	}

	int mx = s, mn = s;
	int idx = par[s];

	//mn = two1[idx].y;

	for(int i = 0; i < t; i++){
		point p = two1[i];
		if(p.x == p.y){
			continue;
		}

		if(mx <= p.x && i >= idx){
			ans += 2 * (p.x - mx);
		}
		mx = max(mx, p.y);
	}

	for(int i = t - 1; i >= 0; i--){
		point p = two1[i];
		if(p.x == p.y){
			continue;
		}

		if(mn >= p.y && i <= idx){
			ans += 2 * (mn - p.y);
		}
		mn = min(mn, p.x);
	}

	/*if(ans == 2782){
		return last;
	}*/
 
	return ans;
}
 
/*int main(){
	int n, s;
 
	cin >> n >> s;
 
	vector<int> p;
	for(int i = 0; i < n; i++){
		int x;
 
		cin >> x;
 
		p.push_back(x);
	}
 
	cout << minimum_walk(p, s) << "\n";
 
	return 0;
}*/

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