oj.uz

Submission #69567

# Submission time Handle Problem Language Result Execution time Memory
69567 2018-08-21T09:02:48 Z Noam527 Ancient Books (IOI17_books) C++17
50 / 100
 427 ms 28572 KB 
#include "books.h"
#include <bits/stdc++.h>
#define endl '\n'
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define debug cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
const ll hs = 199;
const ldb eps = 1e-9, pi = acos(-1);
using namespace std;

int n;
vector<int> a, vis, to;

int cycle(int st) {
	vis[st] = 1;
	int rtn = st;
	st = a[st];
	while (!vis[st]) {
		rtn = max(rtn, st);
		vis[st] = 1;
		st = a[st];
	}
	return rtn;
}
vector<int> cycle2(int st) {
	vis[st] = 1;
	vector<int> rtn = { st };
	st = a[st];
	while (!vis[st]) {
		rtn.push_back(st);
		vis[st] = 1;
		st = a[st];
	}
	return rtn;
}

ll minimum_walk(vector<int> p, int s) {
	n = p.size();
	a = p;
	ll sum = 0;
	for (int i = 0; i < n; i++)
		sum += abs(i - a[i]);

	int l = 0, r = n - 1;
	while (l < n && a[l] == l) l++;
	if (l == n) return 0;
	while (a[r] == r) r--;



	vis.resize(n, 0);
	to.resize(n, -1);
	for (int i = l; i <= r; i++)
		if (!vis[i])
			to[i] = cycle(i);
	vector<pair<int, int>> st;
	for (int i = l; i <= r; i++)
		if (to[i] != -1) {
			if (!st.size()) st.push_back({ i, to[i] });
			else {
				if (st.back().second < i) st.push_back({ i, to[i] });
				else st.back().second = max(st.back().second, to[i]);
			}
		}

	ll rtn = sum + 2LL * ((int)st.size() - 1);
	if (s < l) return rtn + 2 * (l - s);
	if (r < s) return rtn + 2 * (s - r);

	for (auto &i : vis) i = 0;
	vector<int> tmp;
	for (const auto &i : st) {
		if (i.first <= s && s <= i.second) {
			ll mn = n;
			tmp = cycle2(i.first);
			for (const auto &j : tmp)
				mn = min(mn, (ll)abs(s - j));
			tmp = cycle2(i.second);
			for (const auto &j : tmp)
				mn = min(mn, (ll)abs(s - j));
			return rtn + 2 * mn;
		}
	}
}

Compilation message

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:87:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
12.0 / 12.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 532 KB Output is correct
7 Correct 2 ms 532 KB Output is correct
8 Correct 3 ms 652 KB Output is correct
9 Correct 2 ms 652 KB Output is correct
10 Correct 2 ms 652 KB Output is correct
11 Correct 3 ms 652 KB Output is correct
12 Correct 2 ms 652 KB Output is correct
13 Correct 3 ms 652 KB Output is correct
14 Correct 3 ms 652 KB Output is correct
15 Correct 2 ms 652 KB Output is correct
16 Correct 4 ms 652 KB Output is correct
17 Correct 2 ms 652 KB Output is correct
18 Correct 2 ms 652 KB Output is correct
19 Correct 2 ms 652 KB Output is correct
20 Correct 2 ms 652 KB Output is correct
21 Correct 3 ms 652 KB Output is correct
22 Correct 3 ms 652 KB Output is correct
23 Correct 2 ms 652 KB Output is correct
24 Correct 3 ms 652 KB Output is correct
25 Correct 2 ms 652 KB Output is correct
26 Correct 2 ms 652 KB Output is correct
27 Correct 3 ms 652 KB Output is correct
28 Correct 2 ms 652 KB Output is correct
29 Correct 2 ms 652 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 532 KB Output is correct
7 Correct 2 ms 532 KB Output is correct
8 Correct 3 ms 652 KB Output is correct
9 Correct 2 ms 652 KB Output is correct
10 Correct 2 ms 652 KB Output is correct
11 Correct 3 ms 652 KB Output is correct
12 Correct 2 ms 652 KB Output is correct
13 Correct 3 ms 652 KB Output is correct
14 Correct 3 ms 652 KB Output is correct
15 Correct 2 ms 652 KB Output is correct
16 Correct 4 ms 652 KB Output is correct
17 Correct 2 ms 652 KB Output is correct
18 Correct 2 ms 652 KB Output is correct
19 Correct 2 ms 652 KB Output is correct
20 Correct 2 ms 652 KB Output is correct
21 Correct 3 ms 652 KB Output is correct
22 Correct 3 ms 652 KB Output is correct
23 Correct 2 ms 652 KB Output is correct
24 Correct 3 ms 652 KB Output is correct
25 Correct 2 ms 652 KB Output is correct
26 Correct 2 ms 652 KB Output is correct
27 Correct 3 ms 652 KB Output is correct
28 Correct 2 ms 652 KB Output is correct
29 Correct 2 ms 652 KB Output is correct
30 Correct 427 ms 25060 KB Output is correct
31 Correct 348 ms 25060 KB Output is correct
32 Correct 141 ms 25060 KB Output is correct
33 Correct 171 ms 28572 KB Output is correct
34 Correct 172 ms 28572 KB Output is correct
35 Correct 188 ms 28572 KB Output is correct
36 Correct 193 ms 28572 KB Output is correct
37 Correct 190 ms 28572 KB Output is correct
38 Correct 193 ms 28572 KB Output is correct
39 Correct 189 ms 28572 KB Output is correct
40 Correct 253 ms 28572 KB Output is correct
41 Correct 239 ms 28572 KB Output is correct
42 Correct 216 ms 28572 KB Output is correct
43 Correct 193 ms 28572 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 28572 KB 3rd lines differ - on the 1st token, expected: '3304', found: '3590'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 532 KB Output is correct
7 Correct 2 ms 532 KB Output is correct
8 Correct 3 ms 652 KB Output is correct
9 Correct 2 ms 652 KB Output is correct
10 Correct 2 ms 652 KB Output is correct
11 Correct 3 ms 652 KB Output is correct
12 Correct 2 ms 652 KB Output is correct
13 Correct 3 ms 652 KB Output is correct
14 Correct 3 ms 652 KB Output is correct
15 Correct 2 ms 652 KB Output is correct
16 Correct 4 ms 652 KB Output is correct
17 Correct 2 ms 652 KB Output is correct
18 Correct 2 ms 652 KB Output is correct
19 Correct 2 ms 652 KB Output is correct
20 Correct 2 ms 652 KB Output is correct
21 Correct 3 ms 652 KB Output is correct
22 Correct 3 ms 652 KB Output is correct
23 Correct 2 ms 652 KB Output is correct
24 Correct 3 ms 652 KB Output is correct
25 Correct 2 ms 652 KB Output is correct
26 Correct 2 ms 652 KB Output is correct
27 Correct 3 ms 652 KB Output is correct
28 Correct 2 ms 652 KB Output is correct
29 Correct 2 ms 652 KB Output is correct
30 Correct 427 ms 25060 KB Output is correct
31 Correct 348 ms 25060 KB Output is correct
32 Correct 141 ms 25060 KB Output is correct
33 Correct 171 ms 28572 KB Output is correct
34 Correct 172 ms 28572 KB Output is correct
35 Correct 188 ms 28572 KB Output is correct
36 Correct 193 ms 28572 KB Output is correct
37 Correct 190 ms 28572 KB Output is correct
38 Correct 193 ms 28572 KB Output is correct
39 Correct 189 ms 28572 KB Output is correct
40 Correct 253 ms 28572 KB Output is correct
41 Correct 239 ms 28572 KB Output is correct
42 Correct 216 ms 28572 KB Output is correct
43 Correct 193 ms 28572 KB Output is correct
44 Incorrect 3 ms 28572 KB 3rd lines differ - on the 1st token, expected: '3304', found: '3590'
45 Halted 0 ms 0 KB -