Submission #1053136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053136		abczz	Ancient Books (IOI17_books)	C++17	100 / 100	89 ms	25280 KiB

books

#include "books.h"
#include <iostream>
#define ll long long

using namespace std;

bool ok = 0;
vector <ll> p;
ll n, l, r, x, y, qx, qy, ql, qr, a, b, f = 0, mn = 0, mx = 0;
void branch() {
	while (true) {
		for	(int i=x; i>=qx; --i) {
			qx = min(qx, p[i]);
			qy = max(qy, p[i]);
		}
		for (int i=y; i<=qy; ++i) {
			qx = min(qx, p[i]);
			qy = max(qy, p[i]);
		}
		if (x == qx && y == qy) break;
		x = qx, y = qy;
	}
}
long long minimum_walk(std::vector<int> A, int s) {
	for (auto u : A) p.push_back(u);
	n = p.size();
	for (int i=0; i<n; ++i) {
		f += abs(i-p[i]);
	}
	l = n, r = -1;
	for (int i=0; i<n; ++i) {
		if (p[i] != i) {
			l = i;
			break;
		}
	}
	for (int i=n-1; i>=0; --i) {
		if (p[i] != i) {
			r = i;
			break;
		}
	}
	if (l == n) return 0;
	x = y = qx = qy = s;
	branch();
	while (true) {
		ok = a = b = 0;
		mn = 1e18, mx = -1e18;
		for (int i=x-1; i>=l; --i) {
			qx = i;
			mn = min(mn, (ll)p[i]);
			if (p[i] > y) {
				a += 2;
				ok = 1;
				break;
			}
			if (mn == i) a += 2;
		}
		for (int i=y+1; i<=r; ++i) {
			qy = i;
			mx = max(mx, (ll)p[i]);
			if (p[i] < x) {
				b += 2;
				break;
			}
			if (mx == i) b += 2;
		}
		if (!ok) {
			f += a + b;
			break;
		}
		else {
			f += min(a, b);
			branch();
		}
	}
	return f;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:47:10: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   47 |   ok = a = b = 0;
      |        ~~^~~~~~~

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