oj.uz

Submission #624607

# Submission time Handle Problem Language Result Execution time Memory
624607 2022-08-08T14:29:56 Z 8e7 Ancient Books (IOI17_books) C++17
0 / 100
 2000 ms 212 KB 
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 1000005
#define pii pair<int, int>
#define ff first
#define ss second
#include "books.h"

const int inf = 1e9;
pii ran[maxn], color[maxn];
long long minimum_walk(vector<int> p, int s) {
	ll ans = 0;
	int n = p.size();
	vector<int> a(n, 0);
	vector<bool> vis(n, 0);
	{
		int c = 0;
		for (int i = 0;i < n;i++) {
			ans += abs(p[i] - i);
			if (!vis[i]) {
				c++;
				int cur = i;
				int mi = inf, ma = 0;
				do {
					mi = min(mi, cur);
					ma = max(ma, cur);
					a[cur] = c;
					vis[cur] = 1;
					cur = p[cur];
				} while (!vis[cur]);
				color[c] = {mi, ma};
			}
		}
		for (int i = 0;i < n;i++) ran[i] = color[a[i]];
	}
	auto expand = [&] (int l, int r, int nl, int nr, int type) { //0:none, 1:left, 2:right
		if (type == 1) {
			l = max(0, l-1);
			nl = min(nl, ran[l].ff);	
			nr = max(nr, ran[l].ss);
		} else if(type == 2) {
			r = min(n-1, r+1);
			nl = min(nl, ran[r].ff);	
			nr = max(nr, ran[r].ss);
		}
		while (nl < l || nr > r) {
			int tl = nl, tr = nr;
			while (tl < l) {
				l--;	
				nl = min(nl, ran[l].ff);
				nr = max(nr, ran[l].ss);
			}
			while (tr > r) {
				r++;
				nl = min(nl, ran[r].ff);
				nr = max(nr, ran[r].ss);
			}
		}
		return make_pair(l, r);
	};
	pii cur = {s, s};	
	cur = expand(s, s, ran[s].ff, ran[s].ss, 0);	
	while (cur.ff != 0 || cur.ss != n-1) {
		if (cur.ff == 0) {
			cur = expand(cur.ff, cur.ss, cur.ff, cur.ss, 2);
			ans+=2;
		} else if (cur.ss == n-1){
			cur = expand(cur.ff, cur.ss, cur.ff, cur.ss, 1);
			ans+=2;
		} else {
			pii tmp = cur, lef;
			int sl = 0, sr = 0, vl, vr;
			while (tmp.ss <= cur.ss) {
				expand(tmp.ff, tmp.ss, tmp.ff, tmp.ss, 1);
				sl++;
				if (tmp.ff == 0) break;
			}
			vl = sl;
			if (tmp.ss <= cur.ss) vl = inf;
			lef = tmp;

			tmp = cur;	
			while (tmp.ff >= cur.ff) {
				expand(tmp.ff, tmp.ss, tmp.ff, tmp.ss, 2);
				sr++;
				if (tmp.ss == n-1) break;
			}
			vr = sr;
			if (tmp.ff >= cur.ff) vr = inf;
			if (vl == inf && vr == inf) {
				ans += 2 * (sl + sr);
				break;
			} else if (vl < vr) {
				ans += 2 * vl;
				cur = lef;
			} else {
				ans += 2 * vr;
				cur = tmp;
			}
		}
	}
	return ans;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2068 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -