Submission #1039163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039163		Soumya1	Ancient Books (IOI17_books)	C++17	100 / 100	101 ms	22904 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
long long minimum_walk(std::vector<int> p, int s) {
	long long ans = 0;
	int n = p.size();
	for (int i = 0; i < n; i++) {
		ans += abs(i - p[i]);
	}
	vector<bool> vis(n);
	vector<int> mn(n, n), mx(n);
	for (int i = 0; i < n; i++) {
		if (vis[i]) continue;
		int cur = i;
		vector<int> all;
		while (!vis[cur]) {
			all.push_back(cur);
			vis[cur] = true;
			mn[i] = min(mn[i], cur);
			mx[i] = max(mx[i], cur);
			cur = p[cur];
		}
		for (int j : all) mn[j] = mn[i], mx[j] = mx[i];
	}
	int L = mn[s], R = mx[s], l = s, r = s;
	auto simulate = [&]() {
		while (L < l || r < R) {
			if (L < l) {
				L = min(L, mn[l]);
				R = max(R, mx[l]);
				l--;
			} else {
				L = min(L, mn[r]);
				R = max(R, mx[r]);
				r++;
			}
		}
	};
	int lto = 0, rto = n - 1;
	for (int i = 0; i < n; i++) {
		if (p[i] == i) lto++;
		else break;
	}
	for (int i = n - 1; i >= 0; i--) {
		if (p[i] == i) rto--;
		else break;
	}
	lto = min(lto, s);
	rto = max(rto, s);
	simulate();
	while (true) {
		bool first = false;
		int right_cost = 0;
		int m = r;
		for (int i = r + 1; i <= rto; i++) {
			if (mn[i] < l) {
				if (i > m) right_cost++;
				first = true;
				break;
			}
			if (mn[i] > m) right_cost++;
			m = max(m, mx[i]); 
		}
		bool second = false;
		int left_cost = 0;
		m = l;
		for (int i = l - 1; i >= lto; i--) {
			if (mx[i] > r) {
				if (i < m) left_cost++;
				second = true;
				break;
			}
			if (mx[i] < m) left_cost++;
			m = min(m, mn[i]);
		}
		if (!first) {
			ans += 2 * (left_cost + right_cost);
			break;
		}
		if (left_cost < right_cost) {
			ans += 2 * left_cost;
			for (int i = r + 1; i <= rto; i++) {
				L = min(L, mn[i]), R = max(R, mx[i]);
				if (mn[i] < l) break;
			}
			simulate();
		} else {
			ans += 2 * right_cost;
			for (int i = l - 1; i >= lto; i--) {				L = min(L, mn[i]), R = max(R, mx[i]);
				if (mx[i] > r) break;
			}
			simulate();
		}
	}
	return ans;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:64:8: warning: variable 'second' set but not used [-Wunused-but-set-variable]
   64 |   bool second = false;
      |        ^~~~~~

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