#include "books.h"
#include <bits/stdc++.h>
using namespace std;
long long minimum_walk(std::vector<int> p, int s) {
long long ans = 0;
int n = p.size();
for (int i = 0; i < n; i++) {
ans += abs(i - p[i]);
}
vector<bool> vis(n);
vector<int> mn(n, n), mx(n);
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
int cur = i;
vector<int> all;
while (!vis[cur]) {
all.push_back(cur);
vis[cur] = true;
mn[i] = min(mn[i], cur);
mx[i] = max(mx[i], cur);
cur = p[cur];
}
for (int j : all) mn[j] = mn[i], mx[j] = mx[i];
}
int L = mn[s], R = mx[s], l = s, r = s;
auto simulate = [&]() {
while (L < l || r < R) {
if (L < l) {
L = min(L, mn[l]);
R = max(R, mx[l]);
l--;
} else {
L = min(L, mn[r]);
R = max(R, mx[r]);
r++;
}
}
};
simulate();
while (true) {
bool first = false;
int right_cost = 0;
int m = r;
for (int i = r + 1; i < n; i++) {
if (mn[i] < l) {
right_cost++;
first = true;
break;
}
if (mn[i] > m) right_cost++;
m = max(m, mx[i]);
}
bool second = false;
int left_cost = 0;
m = l;
for (int i = l - 1; i >= 0; i--) {
if (mx[i] > r) {
left_cost++;
second = true;
break;
}
if (mx[i] < m) left_cost++;
m = min(m, mn[i]);
}
if (!first) {
ans += 2 * (left_cost + right_cost);
break;
}
if (left_cost < right_cost) {
ans += 2 * left_cost;
for (int i = l + 1; i < n; i++) {
L = min(L, mn[i]), R = max(R, mx[i]);
if (mn[i] < l) break;
}
simulate();
} else {
ans += 2 * right_cost;
for (int i = r - 1; i >= 0; i--) {
L = min(L, mn[i]), R = max(R, mx[i]);
if (mx[i] > r) break;
}
simulate();
}
}
return ans;
}
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:53:8: warning: variable 'second' set but not used [-Wunused-but-set-variable]
53 | bool second = false;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '4', found: '6' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '4', found: '6' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '4', found: '6' |
| 6 |
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 |
1 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '5920', found: '5924' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '4', found: '6' |
| 6 |
Halted |
0 ms |
0 KB |
- |
