제출 #65765

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
65765		MatheusLealV	고대 책들 (IOI17_books)	C++17	12 / 100	3 ms	624 KiB

books

#include "books.h"
#define N 1000005
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll ans = 0;

ll n, maior[N], qtd = 0, ok[N], en;

vector<int> g;

void dfs(ll x, ll &mx)
{
	mx = max(mx, maior[x]);

	if(ok[x]) return;

	ok[x] = 1;

	dfs(g[x], mx);
}

ll minimum_walk(vector<int> p, int s)
{
	n = p.size();

	g = p;

	for(ll i = 0; i < n; i++) ans += abs(i - p[i]);

	for(int i = 0; i < n; i++) maior[i] = i;

	for(ll i = 0; i < n; i++) dfs(i, maior[i]);

	for(ll i = n - 1; i >= 0; i--)
	{
		if(p[i] != i)
		{
			en = i;

			break;
		}
	}

	ll pos = 0, qtd = 0;

	while(pos <= en)
	{
		pos = maior[pos] + 1;

		qtd ++;
	}

	return ans + 2*(qtd - 1);
}

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