제출 #1227634

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227634		The_Samurai	고대 책들 (IOI17_books)	C++20	50 / 100	384 ms	55188 KiB

books

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

struct dsu {
	vector<vector<int>> childs;
	vector<int> par;

	void init(int n) {
		childs.assign(n, {});
		par.assign(n, 0);
		for (int i = 0; i < n; i++) par[i] = i, childs[i].emplace_back(i);
	}

	int get(int a) { return par[a]; }

	void merge(int a, int b) {
		if (par[a] == par[b]) return;
		a = par[a]; b = par[b];
		if (childs[a].size() < childs[b].size()) swap(a, b);
		for (int x: childs[b]) {
			par[x] = a;
			childs[a].emplace_back(x);
		}
		childs[b].clear();
	}
};

long long minimum_walk(std::vector<int> p, int s) {
	int n = p.size();
	int until = n - 1;
	while (until >= 0 and p[until] == until) until--;
	ll exp = 0;
	for (int i = 0; i <= until; i++) exp += abs(p[i] - i);
	if (until < 0) return 0;
	exp -= 2;
	set<int> st;
	for (int i = 0; i < n; i++) st.insert(i);
	for (int i = 0; i <= until; i++) {
		exp += 2;
		int mx = i;
		st.erase(i);
		vector<int> vec = {i};
		for (int j = 0; j < vec.size(); j++) {
			mx = max(mx, vec[j]);
			while (true) {
				auto it = st.lower_bound(vec[j]);
				if (it == st.end() or *it > p[vec[j]]) break;
				vec.emplace_back(*it);
				st.erase(it);
			}
		}
		i = mx;
	}
	return exp;
}

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