Submission #1072220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072220		DeathIsAwe	Ancient Books (IOI17_books)	C++17	50 / 100	159 ms	42476 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
bool visited[1000005];
bool visitedgroup[1000005];

long long minimum_walk(vector<int> p, int s) {
	if (s != 0) {return 0;}
	int n = p.size();
	while (n > 0) {
		if (p[n - 1] == n - 1) {
			n--;
		} else {
			break;
		}
	}
	if (n == 0) {
		return 0;
	}
	vector<long long> right(n), dist(n), group(n);
	
	for (int i=0;i<n;i++) {
		visitedgroup[i] = false;
		visited[i] = false;
		dist[i] = 0;
	}
	long long dummer, distcount, maxtrack, groupnum = 0;
	vector<int> temp;
	for (int i=0;i<n;i++) {
		if (visited[i]) {continue;}
		temp.clear();
		dummer = p[i];
		distcount = abs(i - p[i]);
		maxtrack = max(i, p[i]);
		temp.push_back(i);
		while (dummer != i) {
			distcount += abs(dummer - p[dummer]);
			maxtrack = max(maxtrack, (long long)p[dummer]);
			temp.push_back(dummer);
			dummer = p[dummer];
		}
		for (int j: temp) {
			right[j] = maxtrack;
			dist[j] = distcount;
			group[j] = groupnum;
			visited[j] = true;
		}
		groupnum++;
	}
	//for (int i=0;i<n;i++) {
	//	cout << right[i] << ' ';
	//} cout << '\n';
	//for (int i=0;i<n;i++) {
	//	cout << dist[i] << ' ';
	//} cout << '\n';
	

	long long ans = -2, dum = 0;
	while (dum < n) {
		dummer = dum;
		distcount = dist[dum];
		visitedgroup[group[dum]] = true;
		dum = right[dum];
		while (dummer < dum) {
			dummer++;
			if (visitedgroup[group[dummer]]) {continue;}
			distcount += dist[dummer];
			visitedgroup[group[dummer]] = true;
			dum = max(dum, right[dummer]);
		}
		ans += 2 + distcount;
		dum++;
	}

	return ans;
}

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