#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
vector<int> p;
int s;
int n;
int ret;
struct cycle {
int left=1e9, right=-1e9;
set<int> points;
};
bool CycleLess(cycle &a, cycle &b) {
return pair<int, int>{a.left, a.right} < pair<int, int>{b.left, b.right};
}
bool merge(cycle &a, cycle &b) { // a<-b
if (!(a.left < b.left && a.right < b.right && a.right > b.left)) return 0;
if (a.points.size() < b.points.size()) swap(a, b);
a.right = b.right;
for (int i: b.points) a.points.insert(i);
return 1;
}
bool contains(cycle &a, cycle &b) {
return (a.left <= b.left && b.right <= a.right);
}
vector<bool> vis;
cycle getCycle(int v) {
assert(vis[v]==0);
cycle res;
while (vis[v] == 0) {
vis[v] = 1;
res.left = min(res.left, v);
res.right = max(res.right, v);
res.points.insert(v);
ret += abs(v-p[v]);
v = p[v];
}
return res;
}
vector<cycle> mergedCycles;
vector<int> parents;
int dfs(int v, int par) {
parents[v] = par;
int w = v+1;
while (w<(int)mergedCycles.size() && contains(mergedCycles[v], mergedCycles[w])) {
w = dfs(w, v);
}
return w;
}
void solve() {
vis.assign(n, 0);
vector<cycle> cycles;
if (p[s]==s) cycles.push_back({s, s, {s}});
int globLeft=s, globRight=s;
for (int i = 0; i<n; i++) {
if (vis[i]) continue;
cycles.push_back(getCycle(i));
if (cycles.back().left == cycles.back().right) cycles.pop_back();
else {
globLeft = min(globLeft, cycles.back().left);
globRight = max(globRight, cycles.back().right);
}
}
sort(cycles.begin(), cycles.end(), CycleLess);
vector<int> inds;
for (int i = 0; i<(int)(cycles.size())-1; i++) {
if(merge(cycles[i+1], cycles[i])) continue;
inds.push_back(i);
}
inds.push_back((int)(cycles.size())-1);
mergedCycles.clear();
// mergedCycles.push_back({globLeft, globRight, {globLeft, globRight}});
for (int i: inds) mergedCycles.push_back(cycles[i]);
parents.assign(mergedCycles.size(), -1);
for (int i = 0; i<(int)mergedCycles.size(); i=dfs(i, -1));
int pos=-1;
for (int i = 0; i<(int)mergedCycles.size(); i++) {
if (mergedCycles[i].points.count(s)) pos = i;
}
assert(pos!=-1);
vector<pair<int, int>> jump(n);
for (int i = 0; i<n; i++) {
jump[i]={i, i};
}
for (int i: inds) {
for (int j: cycles[i].points) {
jump[j].first = cycles[i].left;
jump[j].second = cycles[i].right;
}
}
// return;
// for(int i: parents) cerr << i << " ";
// cerr << "\n";
while (parents[pos] != -1) {
cycle elem = mergedCycles[pos];
cycle parent = mergedCycles[parents[pos]];
auto goRightPoint = parent.points.lower_bound(elem.left);
auto goLeftPoint = prev(parent.points.upper_bound(elem.right));
assert(parent.points.lower_bound(elem.left) != parent.points.end());
assert(parent.points.upper_bound(elem.right) != parent.points.begin());
// let's hope it'll not go wrong.
int right = *goRightPoint, left = *goLeftPoint;
// if (right <= elem.right || left >= elem.left) {
// pos = parents[pos];
// continue;
// }
int costRight = 0;
int posToRight = elem.right;
while (posToRight < right) {
costRight++;
posToRight = jump[posToRight+1].second;
}
int costLeft = 0;
int posToLeft = elem.left;
while (posToLeft > left) {
costLeft++;
posToLeft = jump[posToLeft-1].first;
}
ret += 2*min(costLeft, costRight);
pos = parents[pos];
}
vector<int> noParent;
for (int i = 0; i<(int)parents.size(); i++) {
if (parents[i] == -1) noParent.push_back(i);
}
for (int i = 0; i<(int)(noParent.size())-1; i++) {
assert(mergedCycles[i+1].left>mergedCycles[i].right);
ret+=2*(mergedCycles[i+1].left-mergedCycles[i].right);
}
}
long long minimum_walk(vector<signed> _p, signed _s) {
ret = 0;
s = _s;
n = _p.size();
p.resize(n); for (int i = 0; i<n; i++) p[i] = _p[i];
solve();
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
212 KB |
Output is correct |
| 19 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 6 |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
212 KB |
Output is correct |
| 19 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 6 |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
392 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3314' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
212 KB |
Output is correct |
| 19 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 6 |
| 20 |
Halted |
0 ms |
0 KB |
- |
