#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
#define cerr if(0) cout
#define cerr2 if(0) cout
int n;
ll minimum_walk(vector<int> p, int s) {
n = size(p);
vector<bool> vis(n, false);
ll cntGroups = -1;
ll ans = 0;
ll cntNotNeeded = 0;
for(ll l = 0, i = 0, r = 0, size = 0, total = 0; r < n; i++) {
if(p[i] != i && !vis[i]) {
ll prev = i;
ll curr = p[i];
while(curr != i) {
cerr << prev << ' ' << curr << ' ' << abs(prev - curr) << '\n';
vis[prev] = true;
vis[curr] = true;
total += abs(prev - curr);
r = max(r, curr);
prev = p[prev];
curr = p[curr];
}
cerr << prev << ' ' << curr << ' ' << abs(prev - curr) << '\n';
size += abs(prev - curr);
cerr << total << '\n';
total += size;
size = 0;
}
vis[i] = true;
if(i == r) {
cerr2 << l << ' ' << r << '\n';
cerr2 << total << '\n';
if(l != r) {
ans += total;
cntNotNeeded = 0;
} else {
cntNotNeeded++;
}
cntGroups++;
l = i+1;
r = i+1;
total = 0;
}
}
cerr2 << ans << ' ' << cntGroups << '\n';
return ans + max(0ll, cntGroups + cntGroups - cntNotNeeded - cntNotNeeded);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |