#include <bits/stdc++.h>
#ifndef DEBUG
#include "books.h"
#endif
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) {
return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) {
return y > x ? (x = y, true) : false;
}
void debug_out() {
cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
cerr << ' ' << A;
debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
for (int i = 0; i < n; ++i) {
cerr << a[i] << ' ';
}
cerr << endl;
}
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
#define debug(...) 1337
#define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T> &v) {
for (auto& x : v) {
stream << x << ' ';
}
return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
return stream << p.first << ' ' << p.second;
}
const int INF32 = 1e9;
ll minimum_walk(vector<int> p, int s) {
int n = p.size();
ll Ans = 0;
for (int i = 0; i < n; ++i) Ans += labs(p[i] - i);
vector<int> cyc(n, -1);
vector<int> cl(n, +INF32), cr(n, -INF32);
int C = 0;
for (int i = 0; i < n; ++i) {
if (p[i] != i && cyc[i] == -1) {
int c = C++;
cl[c] = cr[c] = i;
int x = i;
do {
cyc[x] = c;
chkmax(cr[c], x);
x = p[x];
} while (x != i);
}
}
if (!C) return 0;
vector<int> G[C];
vector<int> GR[C];
for (int c = 0; c < C; ++c) {
for (int i = cl[c]; i <= cr[c]; ++i) {
if (cyc[i] != -1 && cyc[i] != c) {
G[c].push_back(cyc[i]);
GR[cyc[i]].push_back(c);
}
}
}
vector<char> used(C, false);
vector<int> ord;
function<void(int)> dfs = [&](int v) {
used[v] = true;
for (int& u : G[v])
if (!used[u])
dfs(u);
ord.push_back(v);
};
for (int c = 0; c < C; ++c)
if (!used[c])
dfs(c);
reverse(all(ord));
vector<int> scc(C, -1);
int S = 0;
function<void(int)> dfs1 = [&](int v) {
scc[v] = S;
for (int& u : GR[v])
if (scc[u] == -1)
dfs1(u);
};
for (int& v : ord) {
if (scc[v] == -1) {
dfs1(v);
++S;
}
}
vector<char> src(S, true);
for (int c = 0; c < C; ++c) {
for (int d : G[c]) {
if (scc[c] != scc[d]) {
src[scc[d]] = false;
}
}
}
int min_from_s = +INF32;
for (int i = 0; i < n; ++i) {
if (cyc[i] != -1 && src[scc[cyc[i]]]) {
chkmin(min_from_s, labs(i - s));
}
}
Ans += 2 * min_from_s;
vector<int> sl(S, +INF32), sr(S, -INF32);
for (int c = 0; c < C; ++c) {
int s = scc[c];
chkmin(sl[s], cl[c]);
chkmax(sr[s], cr[c]);
}
vector<pii> segs;
for (int s = 0; s < S; ++s) {
if (src[s]) {
segs.emplace_back(sl[s], sr[s]);
}
}
sort(all(segs));
for (int i = 0; i + 1 < segs.size(); ++i) {
int r1 = segs[i].se;
int l2 = segs[i + 1].fi;
assert(r1 < l2);
Ans += 2 * (l2 - r1);
}
if (s != 0) {
bool inside = false;
for (int g : segs) {
if (g.fi <= s && s <= g.se) {
inside = true;
}
}
return inside;
}
return Ans;
}
#ifdef DEBUG
int32_t main() {
#ifdef DEBUG
freopen("in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
int n, s;
cin >> n >> s;
vector<int> p(n);
for (auto& x : p) cin >> x;
cout << minimum_walk(p, s) << '\n';
return 0;
}
#endif
Compilation message
books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:145:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for (int i = 0; i + 1 < segs.size(); ++i) {
| ~~~~~~^~~~~~~~~~~~~
books.cpp:153:18: error: cannot convert 'std::pair<int, int>' to 'int' in initialization
153 | for (int g : segs) {
| ^~~~
books.cpp:8:12: error: request for member 'first' in 'g', which is of non-class type 'int'
8 | #define fi first
| ^~~~~
books.cpp:154:13: note: in expansion of macro 'fi'
154 | if (g.fi <= s && s <= g.se) {
| ^~
books.cpp:9:12: error: request for member 'second' in 'g', which is of non-class type 'int'
9 | #define se second
| ^~~~~~
books.cpp:154:31: note: in expansion of macro 'se'
154 | if (g.fi <= s && s <= g.se) {
| ^~
