#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> cycle;
vector<int> p;
ll n;
ll minc = 1e9;
ll maxc = -1e9;
struct UFDS{
int n;
vector<int> parent;
UFDS(int _n){
n = _n;
parent.resize(n);
for (int i = 0; i<n; i++){
parent[i]=i;
}
}
int root(int i){
if (parent[i]==i){return i;}
return parent[i]=root(parent[i]);
}
void connect(int a, int b){
int ra = root(a);
int rb = root(b);
if (ra==rb){return;}
parent[ra]=rb;
}
bool connected(int a, int b){
return root(a) == root(b);
}
};
ll findcycle(ll i, ll ptr){
cycle[i] = ptr;
minc=min(minc,i);
maxc=max(maxc,i);
if (cycle[p[i]]!=-1){
return abs(i-p[i]);
} else {
return abs(i-p[i]) + findcycle(p[i], ptr);
}
}
ll minimum_walk(std::vector<int> px, int s) {
p = px;
n = p.size();
cycle.resize(n,-1);
ll cycledist = 0;
ll ptr = 0;
vector<pair<int,int>> cycleranges;
vector<ll> cyclewidth(n+1);
for (ll i = 0; i<n; i++){
if (cycle[i]!=-1){continue;}
minc=1e9;maxc=-1e9;
ll dist = findcycle(i,ptr);
cycleranges.push_back({minc,maxc});
cyclewidth[minc]++;
cyclewidth[maxc]--;
cycledist+=dist;
ptr++;
}
ll prev = 0;
bool iszero = true;
ll ctr = 0;
ll minabove=1e9;
ll maxbelow=-1e9;
bool isbetween = false;
for (ll i = 0; i<=n; i++){
ctr+=cyclewidth[i];
/*if (ctr==0&&i==s){
isbetween=true;
}*/
if (iszero&&ctr>0){
if (i<=s){
maxbelow=max(maxbelow,i);
}
if (i>=s){
minabove=min(minabove,i);
}
if (prev!=0){cycledist+=2*(i-prev);}
iszero = false;
} else if ((!iszero)&&ctr==0){
if (i-1<=s){
maxbelow=max(maxbelow,i-1);
}
if (i-1>=s){
minabove=min(minabove,i-1);
}
prev = i;
iszero = true;
}
}
//cout<<maxbelow<<' '<<minabove<<endl;
if (maxbelow==-1e9&&minabove==1e9){
return 0;
} else if (!isbetween){
cycledist+=2*(min(abs(minabove-s),abs(s-maxbelow)));
} else {
UFDS u(n);
for (int i = 0; i<n-1; i++){
for (int j = i+1; j<n; j++){
int as = cycleranges[i].first;
int ae = cycleranges[i].second;
int bs = cycleranges[j].first;
int be = cycleranges[j].second;
if ((as<=bs&&bs<=ae&&bs<=ae&&ae<=be)||(bs<=as&&as<=be&&as<=be&&be<=ae)){
u.connect(i,j);
}
}
}
vector<pair<int,int>> ranges(n,{1e9,-1e9});
for (int i = 0; i<n; i++){
int r = u.root(i);
ranges[r].first=min(ranges[r].first,cycleranges[r].first);
ranges[r].second=max(ranges[r].second,cycleranges[r].second);
}
vector<pair<int,int>> intersectingranges;
for (auto p : ranges){
if (p.first==1e9){continue;}
if (p.first<=s&&s<=p.second){
intersectingranges.push_back(p);
}
}
sort(intersectingranges.begin(),intersectingranges.end());
ll dist = 0;
for (int i = 0; i<intersectingranges.size()-1; i++){
dist+=min(intersectingranges[i+1].first-intersectingranges[i].first,
intersectingranges[i].second-intersectingranges[i+1].second);
}
cycledist+=2*dist;
}
return cycledist;
}
Compilation message
simurgh.cpp:1:10: fatal error: books.h: No such file or directory
1 | #include "books.h"
| ^~~~~~~~~
compilation terminated.
