#include "books.h"
#include <algorithm>
using namespace std;
typedef long long llong;
const int max_n = 1e6;
const int max_cycle = max_n / 2 + 1;
int n;
int cycle[max_cycle + 1];
int cycle_l[max_cycle + 1];
int cycle_r[max_cycle + 1];
int group_par[max_cycle + 1];
int cycle_n = 0;
int uf[max_cycle + 1];
int near[max_cycle + 1];
int go_left[max_cycle + 1];
int go_right[max_cycle + 1];
llong go[max_cycle + 1];
int find(int x) {
if (uf[x]) uf[x] = find(uf[x]);
return x;
}
long long minimum_walk(vector<int> p, int s) {
llong dist1 = 0ll;
n = p.size();
for (int i = 0; i < n; ++i) {
dist1 += abs(p[i] - i);
if (p[i] != i && cycle[i] == 0) {
cycle[i] = ++cycle_n;
cycle_l[cycle[i]] = i;
int j = p[i];
while (i != j) {
cycle[j] = cycle[i];
cycle_r[cycle[i]] = max(cycle_r[cycle[i]], j);
j = p[j];
}
}
}
if (dist1 == 0ll) return 0ll;
vector<int> st;
st.push_back(0);
for (int i = 0; i < n; ++i) {
if (p[i] != i) {
if (cycle_l[cycle[i]] == i) st.push_back(cycle[i]);
else {
int c = find(cycle[i]);
while (cycle_l[c] < cycle_l[st.back()]) {
int x = st.back();
st.pop_back();
uf[x] = c;
cycle_r[c] = max(cycle_r[c], cycle_r[x]);
}
if (cycle_r[c] == i) {
st.pop_back();
group_par[c] = st.back();
}
}
}
}
bool contain = false;
int right_cycle = 0;
llong dist2 = 0ll;
int l = n + 1, r = -1;
for (int i = 1; i <= cycle_n; ++i) {
if (group_par[i] != 0) group_par[i] = find(group_par[i]);
if (find(i) == i) {
l = min(l, cycle_l[i]);
r = max(r, cycle_r[i]);
if (cycle_l[i] < s && s < cycle_r[i]) contain = 1;
if (right_cycle != 0 && cycle_r[i] < cycle_r[right_cycle]) continue;
if (right_cycle != 0) dist2 += cycle_l[i] - cycle_r[right_cycle];
right_cycle = i;
}
}
if (!contain && l <= s && s <= r) return dist1 + dist2 * 2;
for (int i = 0; i < n; ++i) {
if (p[i] != i) {
int c = find(cycle[i]);
near[c] = i;
if (group_par[c] != 0 && cycle_l[c] == i)
go_left[c] = i - near[group_par[c]];
else if (cycle_r[c] == i)
near[group_par[c]] = max(near[group_par[c]], i - go_left[c]);
}
}
for (int i = 0; i < n; ++i) {
if (p[i] != i) {
int c = find(cycle[i]);
near[c] = i;
if (group_par[c] != 0 && cycle_r[c] == i)
go_right[c] = near[group_par[c]] - i;
else if (cycle_l[c] == i)
near[group_par[c]] = max(near[group_par[c]], i + go_right[c]);
}
}
for (int i = 1; i <= cycle_n; ++i)
go[i] = min(go_left[i], go_right[i]) + go[group_par[i]];
llong dist3 = 1e18;
for (int i = 0; i < n; ++i) {
if (p[i] != i)
dist3 = min(go[find(cycle[i])] + abs(i - s), dist3);
}
return dist1 + (dist2 + dist3) * 2;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 2 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 3 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 4 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 5 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 6 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 7 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 8 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 9 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 10 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 11 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 12 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 13 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 14 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 15 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 16 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 17 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 18 |
Correct |
0 ms |
21464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 2 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 3 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 4 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 5 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 6 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 7 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 8 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 9 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 10 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 11 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 12 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 13 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 14 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 15 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 16 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 17 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 18 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 19 |
Incorrect |
0 ms |
21464 KB |
3rd lines differ - on the 1st token, expected: '338572', found: '336580' |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 2 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 3 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 4 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 5 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 6 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 7 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 8 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 9 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 10 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 11 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 12 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 13 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 14 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 15 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 16 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 17 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 18 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 19 |
Incorrect |
0 ms |
21464 KB |
3rd lines differ - on the 1st token, expected: '338572', found: '336580' |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
21464 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '2740' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 2 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 3 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 4 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 5 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 6 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 7 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 8 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 9 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 10 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 11 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 12 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 13 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 14 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 15 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 16 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 17 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 18 |
Correct |
0 ms |
21464 KB |
Output is correct |
| 19 |
Incorrect |
0 ms |
21464 KB |
3rd lines differ - on the 1st token, expected: '338572', found: '336580' |
| 20 |
Halted |
0 ms |
0 KB |
- |
