#include <bits/stdc++.h>
#include "books.h"
using namespace std;
using ll = long long;
long long minimum_walk(std::vector<int> p, int s) {
if (is_sorted(p.begin(), p.end())) {
return 0;
}
int n = p.size();
ll ans = 0;
vector<int> inv(n);
for (int i = 0; i < n; ++i) {
inv[p[i]] = i;
ans += abs(p[i] - i);
}
vector<int> lx(n, -1), rx(n, -1);
for (int i = 0; i < n; ++i) {
if (lx[i] == -1) {
int v = i, mn = n, mx = 0;
vector<int> cycle;
do {
mn = min(mn, v);
mx = max(mx, v);
lx[v] = 228;
cycle.push_back(v);
v = p[v];
} while (lx[v] == -1);
for (int x: cycle) {
lx[x] = mn, rx[x] = mx;
}
}
}
auto extend = [&](int &l, int &r, int limL, int limR) {
int mn = l, mx = r;
for (int i = l; i <= limL; ++i) {
mn = min(mn, lx[i]);
mx = max(mx, rx[i]);
}
for (int i = limR; i <= r; ++i) {
mn = min(mn, lx[i]);
mx = max(mx, rx[i]);
}
l = mn, r = mx;
};
int trivL = 0, trivR = n - 1;
while (p[trivL] == trivL) {
trivL += 1;
}
while (p[trivR] == trivR) {
trivR -= 1;
}
int l = lx[s], r = rx[s];
extend(l, r, s, s);
while (l >= 0 && r < n) {
int cl = l, cr = r;
int ansL = 0, ansR = 0;
int mn = n;
bool found = false;
while (cl > 0) {
cl -= 1;
if (mn > cl) {
ansL += 1;
}
mn = min(mn, p[cl]);
if (rx[cl] > r) {
found = true;
break;
}
}
int mx = 0;
while (cr < n - 1) {
cr += 1;
if (mx < cr) {
ansR += 1;
}
mx = max(mx, p[cr]);
if (lx[cr] < l) {
found = true;
break;
}
}
if (!found) {
if (trivL < l) {
ans += (ansL - trivL) * 2;
}
if (trivR > r) {
ans += (ansR - (n - trivR - 1)) * 2;
}
break;
}
ans += min(ansL, ansR) * 2;
int pl = l, pr = r;
l = min(lx[cl], lx[cr]);
r = max(rx[cr], rx[cr]);
extend(l, r, pl, pr);
}
return ans;
}
Compilation message
books.cpp:3:1: error: extended character is not valid in an identifier
3 |
| ^
books.cpp:6:1: error: extended character is not valid in an identifier
6 |
| ^
books.cpp:11:1: error: extended character is not valid in an identifier
11 |
| ^
books.cpp:13:1: error: extended character is not valid in an identifier
13 |
| ^
books.cpp:15:1: error: extended character is not valid in an identifier
15 |
| ^
books.cpp:19:1: error: extended character is not valid in an identifier
19 |
| ^
books.cpp:22:1: error: extended character is not valid in an identifier
22 |
| ^
books.cpp:27:1: error: extended character is not valid in an identifier
27 |
| ^
books.cpp:32:1: error: extended character is not valid in an identifier
32 |
| ^
books.cpp:35:1: error: extended character is not valid in an identifier
35 |
| ^
books.cpp:38:1: error: extended character is not valid in an identifier
38 |
| ^
books.cpp:44:1: error: extended character is not valid in an identifier
44 |
| ^
books.cpp:57:1: error: extended character is not valid in an identifier
57 |
| ^
books.cpp:65:1: error: extended character is not valid in an identifier
65 |
| ^
books.cpp:70:1: error: extended character is not valid in an identifier
70 |
| ^
books.cpp:73:1: error: extended character is not valid in an identifier
73 |
| ^
books.cpp:86:1: error: extended character is not valid in an identifier
86 |
| ^
books.cpp:88:1: error: extended character is not valid in an identifier
88 |
| ^
books.cpp:100:1: error: extended character is not valid in an identifier
100 |
| ^
books.cpp:110:1: error: extended character is not valid in an identifier
110 |
| ^
books.cpp:117:1: error: extended character is not valid in an identifier
117 |
| ^
books.cpp:3:1: error: '\U000000a0' does not name a type
3 |
| ^
books.cpp:6:1: error: '\U000000a0' does not name a type
6 |
| ^
