//#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);
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;
u = p[u];
} 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 += col[s] != col[v] && 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], dis[col[u]] = d);
}
}
if (v < r && d + 1 < dis[col[v + 1]]) {
q.emplace_back(col[v + 1], dis[col[v + 1]] = d + 1);
}
if (v > l && d + 1 < dis[col[v - 1]]) {
q.emplace_back(col[v - 1], dis[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]] == i;
cnt -= min[col[i]] == i;
}
cnt = 0;
for (int i = l; i <= r; i++) {
dr += !cnt && s < i;
cnt -= max[col[i]] == i;
cnt += min[col[i]] == i;
}
return ans + dr * 2;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '6', found: '8' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '6', found: '8' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '6', found: '8' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '2750' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '6', found: '8' |
| 2 |
Halted |
0 ms |
0 KB |
- |
