Submission #941527

#	Time	Username	Problem	Language	Result	Execution time	Memory
941527		beaboss	Ancient Books (IOI17_books)	C++14	50 / 100	122 ms	17164 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) {
		// cout << i << endl;
		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;
	// cout << 'd' << endl;
	// cout << ans << endl;
	ans += 2 * (max(st - s, 0) + max(s - en, 0));
	s = min(max(s, st), en);
	// cout << ans << endl;

	int l = s, r = s;
	// cout << ans << endl;
	while (l > st || r < en) {
		// cout << l << r << endl;
		int right = r, left = l;

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

		right=max(right, tr);
		left=min(left, tl);

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

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

		left = min(left, tl);
		right = max(right, tr);
		// if (tr <= s) ans += cl; // didn't get through

		// cout << cl << cr << endl;
		// cout << ans << endl;
		if (tl >= l || tr <= r) ans += cr + 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);

// 	// FOR(i, 0, 8) {
// 	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// 	int n = 100;
// 	vi here(n);
// 	FOR(i, 0, n) here[i] = i;
// 	shuffle(here.begin(), here.end(), rng);
// 	FOR(i, 0, n) cout << here[i] << ' ';
// 	cout << endl;
// 	// vi here = {0, 5, 3, 8, 4, 9, 2, 1, 6, 7 };
// 	int res = minimum_walk(here, 4);
// 	int res2 = minimum_walk2(here, 4);
// 	cout << res << ' ' << res2 << endl;
// 	// cout << res << ' ' << res2 << endl;
// 	// }
// }

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