# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
412945 | 2021-05-27T20:36:45 Z | Pichon5 | Ancient Books (IOI17_books) | C++17 | 0 ms | 0 KB |
#include<bits/stdc++.h> #define ll long long int #define pb push_back #define vi vector<int> using namespace std; ll minimum_walk(vector<int> p,int s){ ll res=0; int n=p.size(); vi cant(n+2,0); for(int i=0;i<n;i++){ if(p[i]==i)continue; res+=abs(i-p[i]); int mi=min(i,p[i]); int ma=max(i,p[i]); cant[mi]++; cant[ma+1]--; } int sum=0; int acum=0; for(int i=0;i<n;i++){ acum+=cant[i]; if(acum==0){ sum++; }else{ res+=2*sum; sum=0; } } return res; } int main(){ int n,x; cin>>n; vi v; for(int i=0;i<n;i++){ cin>>x; v.pb(x); } cout<<minimum_walk(v,0)<<endl; return 0; }