Submission #65764

#	Time	Username	Problem	Language	Result	Execution time	Memory
65764		MatheusLealV	Ancient Books (IOI17_books)	C++17	12 / 100	4 ms	900 KiB

books

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

ll ans = 0;

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

vector<int> g;

void dfs(int x, int &mx)
{
	mx = max(mx, 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(int i = 0; i < n; i++) ans += abs(i - p[i]);

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

	for(int 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