#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 (!(b.left < a.left && b.right < a.right && b.right > a.left)) return 0;
// if (a.points.size() < b.points.size()) swap(a, b);
a.left = b.left;
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;
set<pair<int, int>> pq;
for (int i = 0; i<(int)(cycles.size()); i++) {
auto pointer = pq.lower_bound({cycles[i].left, -1e9});
vector<pair<int, int>> toErase, toInsert;
while (pointer != pq.end() && (*pointer).first <= cycles[i].right) {
toErase.push_back(*pointer);
merge(cycles[i], cycles[(*pointer).second]);
pointer++;
}
for (auto i: toErase) pq.erase(i);
pq.insert({cycles[i].right, i});
}
for (auto i: pq) inds.push_back(i.second);
sort(inds.begin(), inds.end());
mergedCycles.clear();
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[noParent[i+1]].left>mergedCycles[noParent[i]].right);
ret+=2*(mergedCycles[noParent[i+1]].left-mergedCycles[noParent[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 |
1 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 |
260 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 |
1 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 |
1 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 |
260 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 |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
0 ms |
212 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
340 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| 25 |
Runtime error |
2 ms |
724 KB |
Execution killed with signal 6 |
| 26 |
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 |
1 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 |
260 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 |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
0 ms |
212 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
340 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| 25 |
Runtime error |
2 ms |
724 KB |
Execution killed with signal 6 |
| 26 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Runtime error |
1 ms |
724 KB |
Execution killed with signal 6 |
| 7 |
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 |
1 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 |
260 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 |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
0 ms |
212 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
340 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| 25 |
Runtime error |
2 ms |
724 KB |
Execution killed with signal 6 |
| 26 |
Halted |
0 ms |
0 KB |
- |
