#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 g = 0; g < 5; g++) {
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;
}
| # |
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 |
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 |
1 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 |
1 ms |
344 KB |
Output is correct |
| 14 |
Correct |
1 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 |
600 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 |
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 |
1 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 |
1 ms |
344 KB |
Output is correct |
| 14 |
Correct |
1 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 |
600 KB |
Output is correct |
| 19 |
Correct |
1 ms |
344 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 |
348 KB |
Output is correct |
| 23 |
Correct |
1 ms |
348 KB |
Output is correct |
| 24 |
Correct |
0 ms |
348 KB |
Output is correct |
| 25 |
Correct |
1 ms |
348 KB |
Output is correct |
| 26 |
Correct |
0 ms |
348 KB |
Output is correct |
| 27 |
Correct |
0 ms |
348 KB |
Output is correct |
| 28 |
Correct |
0 ms |
348 KB |
Output is correct |
| 29 |
Correct |
1 ms |
348 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 |
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 |
1 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 |
1 ms |
344 KB |
Output is correct |
| 14 |
Correct |
1 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 |
600 KB |
Output is correct |
| 19 |
Correct |
1 ms |
344 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 |
348 KB |
Output is correct |
| 23 |
Correct |
1 ms |
348 KB |
Output is correct |
| 24 |
Correct |
0 ms |
348 KB |
Output is correct |
| 25 |
Correct |
1 ms |
348 KB |
Output is correct |
| 26 |
Correct |
0 ms |
348 KB |
Output is correct |
| 27 |
Correct |
0 ms |
348 KB |
Output is correct |
| 28 |
Correct |
0 ms |
348 KB |
Output is correct |
| 29 |
Correct |
1 ms |
348 KB |
Output is correct |
| 30 |
Correct |
98 ms |
26296 KB |
Output is correct |
| 31 |
Correct |
98 ms |
27240 KB |
Output is correct |
| 32 |
Correct |
97 ms |
8192 KB |
Output is correct |
| 33 |
Correct |
153 ms |
33960 KB |
Output is correct |
| 34 |
Correct |
112 ms |
32512 KB |
Output is correct |
| 35 |
Correct |
135 ms |
35736 KB |
Output is correct |
| 36 |
Correct |
108 ms |
36760 KB |
Output is correct |
| 37 |
Correct |
97 ms |
28856 KB |
Output is correct |
| 38 |
Correct |
140 ms |
27216 KB |
Output is correct |
| 39 |
Correct |
106 ms |
26880 KB |
Output is correct |
| 40 |
Correct |
105 ms |
25288 KB |
Output is correct |
| 41 |
Correct |
112 ms |
25136 KB |
Output is correct |
| 42 |
Correct |
102 ms |
25084 KB |
Output is correct |
| 43 |
Execution timed out |
2064 ms |
35584 KB |
Time limit exceeded |
| 44 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '5920', found: '5922' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
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 |
1 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 |
1 ms |
344 KB |
Output is correct |
| 14 |
Correct |
1 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 |
600 KB |
Output is correct |
| 19 |
Correct |
1 ms |
344 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 |
348 KB |
Output is correct |
| 23 |
Correct |
1 ms |
348 KB |
Output is correct |
| 24 |
Correct |
0 ms |
348 KB |
Output is correct |
| 25 |
Correct |
1 ms |
348 KB |
Output is correct |
| 26 |
Correct |
0 ms |
348 KB |
Output is correct |
| 27 |
Correct |
0 ms |
348 KB |
Output is correct |
| 28 |
Correct |
0 ms |
348 KB |
Output is correct |
| 29 |
Correct |
1 ms |
348 KB |
Output is correct |
| 30 |
Correct |
98 ms |
26296 KB |
Output is correct |
| 31 |
Correct |
98 ms |
27240 KB |
Output is correct |
| 32 |
Correct |
97 ms |
8192 KB |
Output is correct |
| 33 |
Correct |
153 ms |
33960 KB |
Output is correct |
| 34 |
Correct |
112 ms |
32512 KB |
Output is correct |
| 35 |
Correct |
135 ms |
35736 KB |
Output is correct |
| 36 |
Correct |
108 ms |
36760 KB |
Output is correct |
| 37 |
Correct |
97 ms |
28856 KB |
Output is correct |
| 38 |
Correct |
140 ms |
27216 KB |
Output is correct |
| 39 |
Correct |
106 ms |
26880 KB |
Output is correct |
| 40 |
Correct |
105 ms |
25288 KB |
Output is correct |
| 41 |
Correct |
112 ms |
25136 KB |
Output is correct |
| 42 |
Correct |
102 ms |
25084 KB |
Output is correct |
| 43 |
Execution timed out |
2064 ms |
35584 KB |
Time limit exceeded |
| 44 |
Halted |
0 ms |
0 KB |
- |
