Submission #941503

#	Time	Username	Problem	Language	Result	Execution time	Memory
941503		beaboss	Ancient Books (IOI17_books)	C++14	0 / 100	1 ms	4444 KiB

books

// Source: https://oj.uz/problem/view/IOI17_books
// 
#include "books.h"
#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i<b; i++)

bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }

bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }

const int N = 1e6 + 10;
int ri[N], le[N];
bool vis[N];

ll minimum_walk(vector<int> p, int s) {
	// if (s == 0) {
	ll ans = 0;
	int n = p.size();
	FOR(i, 0, n) {
		if (!vis[i]) {
			int l, r;
			r = l = i;
			int cur = p[i];
			while (cur != i) {
				l = min(l, cur);r=max(r, cur);
				cur=p[cur];
			}
			cur = i;
			do {

				ans += abs(p[cur]-cur);
				le[cur] = l;
				ri[cur] = r;
				vis[cur]=true;
				cur=p[cur];
			} while (cur != i);
		}
	}

	int en = n-1;
	while (en != -1 && p[en] == en) en--;
	int st = 0;
	while (st != n && p[st] == st) st++;

	if (st > en) return 0;

	int l = s, r = s;

	while (l > st || r < en) {
		// cout << l << r << endl;
		int tr = r;
		int hr = ri[tr];
		int tl = le[tr];
		int cr = 0;
		while (tr < en && (tl >= s || tr != hr)) {
			// cout << tl << tr << endl;
			if (tr == r) cr+=2;
			tr++;
			tl=min(tl,le[tr]);
			hr = max(hr, ri[tr]);
		}

		int right = tr;

		// if (tl >= s) ans += cr; // didn't get through

		tl = l;
		int hl = le[tr];
		tr = ri[tr];
		int cl = 0;
		while (tl > st && (tr <= s || tl != hl)) {
			if (tl == l) cl+=2;
			tl--;
			tr=max(tr, ri[tl]);
			hl = min(hl, le[tr]);
		}

		int left = tl;
		// if (tr <= s) ans += cl; // didn't get through

		// cout << cl << cr << endl;
		// cout << ans << endl;
		if (tl >= s && tr <= s) ans += cr + cl;
		else if (tl >= s) ans += cr;
		else if (tr <= s) ans += cl;
		else ans += min(cl, cr);
		// cout << ans << endl;
		l = left, r = right;
	}
	// cout << ans << endl;

	// int r =0;
	// FOR(i, 0, en+1) {
	// 	if (r < i) {
	// 		r++;
	// 		ans+=2;
	// 	}
	// 	r = max(p[i], r);
	// }
	return ans;
	// } else assert(false);
}



// int main() {
// 	ios::sync_with_stdio(false);
// 	cin.tie(nullptr);

// 	int res = minimum_walk({4, 1, 3, 2},1);
// 	cout << res << endl;
// }

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