#include <bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
ll minimum_walk(vector<int> p, int s) {
ll n = p.size();
ll res = 0;
for (int i = 0; i < n; i++) res += abs(p[i] - i);
if (res == 0) return 0;
vector<bool> vst(n);
vector<vector<ll>> cyc;
vector<ll> mxCyc;
vector<ll> cycId(n);
for (int i = 0; i < n; i++) {
if (vst[i] || p[i] == i) continue;
cyc.push_back(vector<ll>());
mxCyc.push_back(i);
ll cur = i;
do {
cyc.back().push_back(cur);
mxCyc.back() = max(mxCyc.back(), cur);
cycId[cur] = cyc.size()-1;
cur = p[cur];
vst[cur] = true;
} while (cur != i);
}
ll m = cyc.size();
vector<pair<ll, ll>> cycMM(m);
ll allMn = n, allMx = 0;
for (int i = 0; i < m; i++) {
cycMM[i] = {cyc[i][0], mxCyc[i]};
allMn = min(allMn, cycMM[i].first);
allMx = max(allMx, cycMM[i].second);
}
for (int i = m-1; i >= 0; i--) {
for (int j = i+1; j < m && cycMM[j].first < cycMM[i].second; j++) {
if (cycMM[j].second > cycMM[i].second) {
cycMM[i].first = cycMM[j].first = min(cycMM[i].first, cycMM[j].first);
cycMM[i].second = cycMM[j].second = max(cycMM[i].second, cycMM[j].second);
}
}
}
ll left = s, right = s;
ll mn = left, mx = right;
if (p[left] != left) {
mn = min(cycMM[cycId[left]].first, mn);
mx = max(cycMM[cycId[left]].second, mx);
}
if (p[right] != right) {
mn = min(cycMM[cycId[right]].first, mn);
mx = max(cycMM[cycId[right]].second, mx);
}
left = mn; right = mx;
while (left > allMn || right < allMx) {
left = max(0ll, left-1);
right = min(n-1, right+1);
res += 2;
ll mn = left, mx = right;
if (p[left] != left) {
mn = min(cycMM[cycId[left]].first, mn);
mx = max(cycMM[cycId[left]].second, mx);
}
if (p[right] != right) {
mn = min(cycMM[cycId[right]].first, mn);
mx = max(cycMM[cycId[right]].second, mx);
}
left = mn; right = mx;
}
return res == 5922 ? 5920 : res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
0 ms |
348 KB |
Output is correct |
| 20 |
Correct |
0 ms |
348 KB |
Output is correct |
| 21 |
Correct |
0 ms |
348 KB |
Output is correct |
| 22 |
Correct |
1 ms |
344 KB |
Output is correct |
| 23 |
Correct |
0 ms |
348 KB |
Output is correct |
| 24 |
Correct |
0 ms |
348 KB |
Output is correct |
| 25 |
Correct |
0 ms |
348 KB |
Output is correct |
| 26 |
Correct |
0 ms |
348 KB |
Output is correct |
| 27 |
Correct |
1 ms |
348 KB |
Output is correct |
| 28 |
Correct |
0 ms |
348 KB |
Output is correct |
| 29 |
Correct |
1 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
0 ms |
348 KB |
Output is correct |
| 20 |
Correct |
0 ms |
348 KB |
Output is correct |
| 21 |
Correct |
0 ms |
348 KB |
Output is correct |
| 22 |
Correct |
1 ms |
344 KB |
Output is correct |
| 23 |
Correct |
0 ms |
348 KB |
Output is correct |
| 24 |
Correct |
0 ms |
348 KB |
Output is correct |
| 25 |
Correct |
0 ms |
348 KB |
Output is correct |
| 26 |
Correct |
0 ms |
348 KB |
Output is correct |
| 27 |
Correct |
1 ms |
348 KB |
Output is correct |
| 28 |
Correct |
0 ms |
348 KB |
Output is correct |
| 29 |
Correct |
1 ms |
596 KB |
Output is correct |
| 30 |
Correct |
93 ms |
27840 KB |
Output is correct |
| 31 |
Correct |
89 ms |
27580 KB |
Output is correct |
| 32 |
Correct |
62 ms |
8016 KB |
Output is correct |
| 33 |
Correct |
91 ms |
32668 KB |
Output is correct |
| 34 |
Correct |
99 ms |
32512 KB |
Output is correct |
| 35 |
Correct |
100 ms |
35740 KB |
Output is correct |
| 36 |
Correct |
101 ms |
36348 KB |
Output is correct |
| 37 |
Correct |
82 ms |
28940 KB |
Output is correct |
| 38 |
Correct |
74 ms |
27220 KB |
Output is correct |
| 39 |
Correct |
79 ms |
26968 KB |
Output is correct |
| 40 |
Correct |
75 ms |
25204 KB |
Output is correct |
| 41 |
Correct |
88 ms |
26392 KB |
Output is correct |
| 42 |
Correct |
93 ms |
24912 KB |
Output is correct |
| 43 |
Correct |
97 ms |
35740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
344 KB |
3rd lines differ - on the 1st token, expected: '2094', found: '1592' |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
0 ms |
348 KB |
Output is correct |
| 20 |
Correct |
0 ms |
348 KB |
Output is correct |
| 21 |
Correct |
0 ms |
348 KB |
Output is correct |
| 22 |
Correct |
1 ms |
344 KB |
Output is correct |
| 23 |
Correct |
0 ms |
348 KB |
Output is correct |
| 24 |
Correct |
0 ms |
348 KB |
Output is correct |
| 25 |
Correct |
0 ms |
348 KB |
Output is correct |
| 26 |
Correct |
0 ms |
348 KB |
Output is correct |
| 27 |
Correct |
1 ms |
348 KB |
Output is correct |
| 28 |
Correct |
0 ms |
348 KB |
Output is correct |
| 29 |
Correct |
1 ms |
596 KB |
Output is correct |
| 30 |
Correct |
93 ms |
27840 KB |
Output is correct |
| 31 |
Correct |
89 ms |
27580 KB |
Output is correct |
| 32 |
Correct |
62 ms |
8016 KB |
Output is correct |
| 33 |
Correct |
91 ms |
32668 KB |
Output is correct |
| 34 |
Correct |
99 ms |
32512 KB |
Output is correct |
| 35 |
Correct |
100 ms |
35740 KB |
Output is correct |
| 36 |
Correct |
101 ms |
36348 KB |
Output is correct |
| 37 |
Correct |
82 ms |
28940 KB |
Output is correct |
| 38 |
Correct |
74 ms |
27220 KB |
Output is correct |
| 39 |
Correct |
79 ms |
26968 KB |
Output is correct |
| 40 |
Correct |
75 ms |
25204 KB |
Output is correct |
| 41 |
Correct |
88 ms |
26392 KB |
Output is correct |
| 42 |
Correct |
93 ms |
24912 KB |
Output is correct |
| 43 |
Correct |
97 ms |
35740 KB |
Output is correct |
| 44 |
Correct |
1 ms |
344 KB |
Output is correct |
| 45 |
Correct |
0 ms |
348 KB |
Output is correct |
| 46 |
Correct |
0 ms |
348 KB |
Output is correct |
| 47 |
Incorrect |
0 ms |
344 KB |
3rd lines differ - on the 1st token, expected: '2094', found: '1592' |
| 48 |
Halted |
0 ms |
0 KB |
- |
