Submission #1185062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185062		hamzabc	Ancient Books (IOI17_books)	C++20	50 / 100	118 ms	26044 KiB

books

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


using namespace std;


vector<int> dsu;
vector<int> l;
vector<int> r;
vector<int> used;
vector<pair<int, int>> araliklar;


int goDSU(int a){
	if (dsu[a] == a)
		return a;
	dsu[a] = goDSU(dsu[a]);
	return dsu[a];
}


long long minimum_walk(std::vector<int> p, int s) {
	int n = p.size();
	long long int ret = 0;
	if (p[s] == s){
		int add = 1e9;
		cerr << add << endl;
		for (int i = s; i < n; i++){
			if (p[i] != i){
				add = i - s;
				break;
			}
		}
		for (int i = s; i >= 0; i--){
			if (p[i] != i){
				if (add > s - i){
					add = s - i;
				}
				break;
			}
		}
		if (add != 1e9)
			ret += add * 2;
	}
	dsu.resize(n);
	l.resize(n);
	r.resize(n);
	used.resize(n);
	for (int i = 0; i < n; i++){
		p[i];
		dsu[i] = i;
		l[i] = i;
		r[i] = i;
	}
	for (int i = 0; i < n; i++){
		ret += abs(p[i] - i);
		if (goDSU(i) != goDSU(p[i])){
			r[goDSU(p[i])] = max(r[goDSU(p[i])], r[goDSU(i)]);
			l[goDSU(p[i])] = min(l[goDSU(p[i])], l[goDSU(i)]);
			dsu[goDSU(i)] = goDSU(p[i]);
		}
	}
	for (int i = 0; i < n; i++){
		if (!used[goDSU(i)] && l[goDSU(i)] != r[goDSU(i)]){
			used[goDSU(i)] = true;
			araliklar.push_back({ l[goDSU(i)], r[goDSU(i)] });
		}
	}
	sort(araliklar.begin(), araliklar.end());
	int mxr = araliklar[0].second;
	for (int i = 1; i < araliklar.size(); i++){
		if (mxr > araliklar[i].first){
			mxr = max(mxr, araliklar[i].second);
		}else{
			ret += abs(araliklar[i].first - mxr) * 2;
			mxr = max(mxr, araliklar[i].second);
		}
	}
	return ret;
}

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