Submission #921296

#	Time	Username	Problem	Language	Result	Execution time	Memory
921296		siewjh	Ancient Books (IOI17_books)	C++17	12 / 100	2 ms	8024 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1'000'005;
int cyc[MAXN], lc[MAXN], rc[MAXN];
void extend(int &cl, int &cr, int tl, int tr){
	while (cl > tl || cr < tr){
		if (cl > tl){
			cl--;
			tl = min(tl, lc[cyc[cl]]); tr = max(tr, rc[cyc[cl]]);
		}
		else{
			cr++;
			tl = min(tl, lc[cyc[cr]]); tr = max(tr, rc[cyc[cr]]);
		}
	}
}
ll minimum_walk(vector<int> p, int s) {
	int nums = p.size();
	int mn = s, mx = s;
	memset(cyc, -1, sizeof(cyc));
	ll ans = 0;
	for (int i = 0; i < nums; i++) ans += abs(i - p[i]);
	for (int i = 0; i < nums; i++)
		if (cyc[i] == -1){
			int curr = i, l = i, r = i;
			do{
				cyc[curr] = i; l = min(l, curr); r = max(r, curr);
				curr = p[curr];
			} while (curr != i);
			lc[i] = l; rc[i] = r;
			if (p[i] != i){
				mn = min(mn, l); mx = max(mx, r);
			}
		}
	int cl = lc[cyc[s]], cr = rc[cyc[s]];
	while (cl > mn || cr < mx){
		int lnl = cl, lnr = cr, le = 0;
		while (lnl > mn && lnr <= cr){
			extend(lnl, lnr, lnl - 1, lnr);
			le++;
		}
		int rnl = cl, rnr = cr, re = 0;
		while (rnr < mx && rnl >= cl){
			extend(rnl, rnr, rnl, rnr + 1);
			re++;
		}
		if (lnl == rnl && lnr == rnr){ // cross the middle
			ans += 2 * min(le, re);
			cl = lnl; cr = lnr;
		}
		else{
			ans += 2 * (le + re);
			cl = lnl; cr = rnr;
		}
	}
	return ans;
}

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