oj.uz

Submission #566487

# Submission time Handle Problem Language Result Execution time Memory
566487 2022-05-22T10:59:26 Z Temmie Ancient Books (IOI17_books) C++17
0 / 100
 1 ms 340 KB 
//#include "public_c/public/cpp/books.h"
#include "books.h"

#include <bits/stdc++.h>

long long minimum_walk(std::vector <int> p, int s) {
	int n = p.size();
	std::vector <int> min(n, 1 << 30);
	std::vector <int> max(n, 1 << 30);
	std::vector <int> col(n, -1);
	for (int i = 0, cnt = 0; i < n; i++) {
		if (col[i] != -1) {
			continue;
		}
		int u = i;
		do {
			min[cnt] = std::min(min[cnt], u);
			max[cnt] = std::max(max[cnt], u);
			col[u] = cnt;
		} while (u != i);
		cnt++;
	}
	int l = 0, r = n - 1;
	while (l < s && l == p[l]) {
		l++;
	}
	while (r > s && r == p[r]) {
		r--;
	}
	std::set <int> st;
	for (int i = l; i <= r; i++) {
		st.insert(i);
	}
	int dr = 0;
	std::vector <int> dis(n, 1 << 30);
	std::deque <std::pair <int, int>> q;
	q.emplace_back(col[s], dis[col[s]] = 0);
	while (q.size()) {
		int v = q.front().first;
		int d = q.front().second;
		q.pop_front();
		if (d != dis[v]) {
			continue;
		}
		int mn = min[v];
		int mx = max[v];
		dr += s >= mn && s <= mx;
		while (true) {
			int u;
			auto it = st.lower_bound(mn);
			if (it == st.end() || (u = *it) > mx) {
				break;
			}
			st.erase(it);
			if (d < dis[col[u]]) {
				q.emplace_front(col[u], d);
			}
		}
		if (v + 1 < r && d + 1 < dis[col[v + 1]]) {
			dis[col[v + 1]] = d + 1;
			q.emplace_back(col[v + 1], d + 1);
		}
		if (v - 1 > l && d + 1 < dis[col[v - 1]]) {
			dis[col[v - 1]] = d + 1;
			q.emplace_back(col[v - 1], d + 1);
		}
	}
	long long ans = 0;
	for (int i = l; i <= r; i++) {
		ans += abs(i - p[i]);
	}
	int cnt = 0;
	for (int i = l; i <= r; i++) {
		dr += !cnt && s < i;
		cnt += max[col[i]] > s;
		cnt -= min[col[i]] < s;
	}
	cnt = 0;
	for (int i = l; i <= r; i++) {
		dr += !cnt && s < i;
		cnt -= max[col[i]] > s;
		cnt += min[col[i]] < s;
	}
	return ans + dr * 2;
}

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 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
4 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 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
4 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 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB 3rd lines differ - on the 1st token, expected: '3304', found: '3594'
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 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
4 Halted 0 ms 0 KB -