Submission #125032

#	Time	Username	Problem	Language	Result	Execution time	Memory
125032		Sorting	Ancient Books (IOI17_books)	C++14	12 / 100	3 ms	408 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[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];
	}

	int last = 0;

	for(int i = 0; i < n; i++){
		if(!used[i]){
			v.clear();
			dfs(i);

			if(v.size() > 2){
				last = i;
			}
			else{
				if(v.size() == 2){
					two1.push_back(point(v[0], v[1], i));
					poss[i] = true;
				}
			}

			for(int j = 0; j < (int)v.size() - 1; j++){
				ans += abs(v[j] - v[j + 1]);
				if(v.size() != 2){
					two2.push_back(point(v[j], v[j + 1], -1));
				}
			}
			if(v.size() != 1){
				ans += abs(v[0] - v.back());
				if(v.size() != 2){
					two2.push_back(point(v[0], v.back(), -1));
				}
			}
		}
	}

	for(point p1: two1){
		bool ok = true;

		for(point p2: two2){
			if(between(p1.x, p1.y, p2.x, p2.y)){
				ok = false;
				break;
			}
		}
		for(point p2: two1){
			if(between(p1.x, p1.y, p2.x, p2.y)){
				ok = false;
				break;
			}
		}

		if(ok){
			last = max(last, p1.idx);
		}
	}

	ans += 2 * last;

	return ans;
}

/*int main(){
	int n;

	cin >> n;

	vector<int> p;
	for(int i = 0; i < n; i++){
		int x;

		cin >> x;

		p.push_back(x);
	}

	cout << minimum_walk(p, 0) << "\n";

	return 0;
}*/

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