oj.uz

Submission #415507

# Submission time Handle Problem Language Result Execution time Memory
415507 2021-06-01T07:46:29 Z SeDunion Ancient Books (IOI17_books) C++17
12 / 100
 2 ms 204 KB 
#include "books.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

void extend(int &l, int &r, vector<int>&C, vector<int>&L, vector<int>&R) {
	int ll = l, rr = r;
	for (int i = l ; i <= r ; ++ i) ll = min(ll, L[C[i]]), rr = max(rr, R[C[i]]);
	while (ll != l || rr != r) {
		while (ll < l) {
			--l;
			ll = min(ll, L[C[l]]);
			rr = max(rr, R[C[l]]);
		}
		while (rr > r) {
			++r;
			ll = min(ll, L[C[r]]);
			rr = max(rr, R[C[l]]);
		}
	}
}

ll solve(int l, int r, int needl, int needr, vector<int>&C, vector<int>&L, vector<int>&R) {
	extend(l, r, C, L, R);
	if (needl == l && r == needr) return 0ll;
	int l_l = l, r_l = r; ll c_l = 0;
	while (true) {
		if (l_l <= needl) break;
		if (r_l > r) break;
		c_l += 2;
		--l_l;
		extend(l_l, r_l, C, L, R);
	}
	int l_r = l, r_r = r; ll c_r = 0;
	while (true) {
		if (r_r >= needr) break;
		if (l_r < l) break;
		c_r += 2;
		++r_r;
		extend(l_r, r_r, C, L, R);
	}
	assert((l_r < l) == (r_l > r));
	ll res = 0;
	if (l_r < l) res = min(c_l, c_r);
	else res = c_l + c_r;
	int tl = min(l_l, l_r);
	int tr = max(r_l, r_r);
	res += solve(tl, tr, needl, needr, C, L, R);
	//cerr << l << " " << r << " " << needl << " " << needr << " " << res << "\n";
	return res;
}

ll minimum_walk(vector<int> p, int s) {
	int n = p.size();
	vector<int>C(n, -1), L(n), R(n);
	int l = s, r = s;
	ll essential = 0;
	for (int i = 0 ; i < n ; ++ i) {
		essential += abs(i - p[i]);
		if (C[i] == -1) {
			L[i] = i;
			R[i] = i;
			int j = i;
			do {
				R[i] = max(R[i], j);
				C[j] = i;
				j = p[j];
			} while (i != j);
		}
		if (p[i] != i) l = min(l, i), r = max(r, i);
	}
	return solve(s, s, l, r, C, L, R) + essential;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 2 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 2 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Incorrect 1 ms 204 KB 3rd lines differ - on the 1st token, expected: '338572', found: '338574'
20 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 2 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Incorrect 1 ms 204 KB 3rd lines differ - on the 1st token, expected: '338572', found: '338574'
20 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 2 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Incorrect 1 ms 204 KB 3rd lines differ - on the 1st token, expected: '338572', found: '338574'
20 Halted 0 ms 0 KB -