Submission #768558

#	Time	Username	Problem	Language	Result	Execution time	Memory
768558		SanguineChameleon	Ancient Books (IOI17_books)	C++17	100 / 100	157 ms	22672 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e6 + 20;
int cycleL[maxN];
int cycleR[maxN];

void extend(int &curL, int &curR) {
	int nxtL = min(curL, min(cycleL[curL], cycleL[curR]));
	int nxtR = max(curR, max(cycleR[curL], cycleR[curR]));
	while (curL > nxtL || curR < nxtR) {
		if (curL > nxtL) {
			curL--;
			nxtL = min(nxtL, cycleL[curL]);
			nxtR = max(nxtR, cycleR[curL]);
		}
		else {
			curR++;
			nxtL = min(nxtL, cycleL[curR]);
			nxtR = max(nxtR, cycleR[curR]);
		}
	}
}

long long minimum_walk(vector<int> A, int start) {
	int N = A.size();
	for (int i = 0; i < N; i++) {
		cycleL[i] = -1;
		cycleR[i] = -1;
	}
	int curL = start;
	int curR = start;
	int endL = start;
	int endR = start;
	long long res = 0;
	for (int i = 0; i < N; i++) {
		if (i != A[i]) {
			endL = min(endL, i);
			endR = max(endR, i);
		}
		res += abs(A[i] - i);
		if (cycleL[i] == -1) {
			int L = i;
			int R = i;
			int cur = i;
			do {
				L = min(L, cur);
				R = max(R, cur);
				cur = A[cur];
			}
			while (cur != i);
			cur = i;
			do {
				cycleL[cur] = L;
				cycleR[cur] = R;
				cur = A[cur];
			}
			while (cur != i);
		}
	}
	while (curL > endL || curR < endR) {
		extend(curL, curR);
		int costL = 0;
		int nxtLL = curL;
		int nxtLR = curR;
		while (nxtLL > endL && nxtLR == curR) {
			nxtLL--;
			costL += 2;
			extend(nxtLL, nxtLR);
		}
		int costR = 0;
		int nxtRL = curL;
		int nxtRR = curR;
		while (nxtRR < endR && nxtRL == curL) {
			nxtRR++;
			costR += 2;
			extend(nxtRL, nxtRR);
		}
		if (nxtLR == curR && nxtRL == curL) {
			res += costL + costR;
		}
		else {
			res += min(costL, costR);
		}
		curL = min(nxtLL, nxtRL);
		curR = max(nxtLR, nxtRR);
	}
	return res;
}

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