# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1076030 | amin | Ancient Books (IOI17_books) | C++14 | 1 ms | 440 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
long long minimum_walk(vector<int> p, int s) {
ll ans=0;
ll n=p.size();
int o[n+1];
for(int i=0;i<=n;i++)
{
o[i]=0;
}
int pre=0;
ll mi=1000000;
ll ma=0;
vector<pair<int,int> >r;
for(ll i=0;i<n;i++)
{
if(p[i]!=i&&o[i]==0)
{
ll t=i;
mi=min(mi,i);
ma=i;
ll x=p[i];
o[i]=1;
while(x!=i)
{
t=max(t,x);
o[x]=1;
x=p[x];
}
r.push_back({i,t});
}
ans+=abs(p[i]-i);
}
sort(r.begin(),r.end());
if(r.size()>0)
{
for(int i=0;i<r.size()-1;i++)
{
if(r[i].second>r[i+1].first)
{
r[i+1].first=r[i].first;
r[i+1].second=max(r[i].second,r[i+1].second);
}
}
int o=r.size();
ma=r[o-1].first;
}
if(mi==1000000)
mi=0;
return ans+ma*2;
}
Compilation message (stderr)
# | 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... |