제출 #54188

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54188		radoslav11	고대 책들 (IOI17_books)	C++14	0 / 100	3 ms	564 KiB

books

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

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);

int n;
int p[MAXN];
bool used[MAXN];

pair<int, int> dfs(int u)
{
	used[u] = true;
	pair<int, int> ret = {u, u};

	if(!used[p[u]])
	{
		pair<int, int> oth = dfs(p[u]);
		chkmax(ret.second, oth.second);
		chkmin(ret.first, oth.first);
	}

	return ret;
}

long long minimum_walk(std::vector<int> p, int s) 
{
	if(s != 0) return -1;

	n = p.size();
	for(int i = 0; i < n; i++)
		::p[i] = p[i];

	int64_t answer = 0;
	for(int i = 0; i < n; i++)
		answer += abs(i - p[i]);

	vector<pair<int, int> > li;
	for(int i = 0; i < n; i++)
		if(i != p[i] && !used[i])
			li.push_back(dfs(i));			

	sort(li.begin(), li.end());
	
	vector<pair<int, int> > tmp;
	for(int i = 0; i < n; i++)
		if(tmp.empty() || tmp.back().second < li[i].first) tmp.push_back(li[i]);
		else chkmax(tmp[tmp.size() - 1].second, li[i].second);

	int last = 0;
	for(auto it: li)
	{
		answer += 2 * (it.first - last);
		last = it.second;
	}

	return answer;
}

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