Submission #423184

#	Time	Username	Problem	Language	Result	Execution time	Memory
423184		Pbezz	Ancient Books (IOI17_books)	C++14	50 / 100	180 ms	31684 KiB

books

#include "books.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
typedef pair<ll,ll> pii;

const ll MAXN=2e5+5;
const ll INF=1e9+7;

long long minimum_walk(std::vector<int> p, int s) {

ll i,n=(ll)p.size(),k,count=0,arr[n+10],maxi,ans=0;


pii cycle[n+4]; //cycle[i]={representante left,representante right}
for(i=0;i<n+2;i++){
arr[i]=0;
cycle[i]={0,0};
}

for(i=0;i<n;i++){
if(arr[i]!=0||p[i]==i)continue;

maxi = max(i,(ll)p[i]);
count++;	arr[i]=count;
k=p[i];
cycle[count].first=i;

ans+=abs(k-i);

while(k!=i){
arr[k]=count;
ans+=abs(k-p[k]);
k=p[k];	maxi = max(maxi,k);
}
cycle[count].second=maxi;
}
//cout<<ans<<endl;

if(count==0)return 0;

ll cur=cycle[1].second;
bool f=true;
for(i=2;i<=count;i++){

while(i<=count && cycle[i].first<=cur){
cur=max(cur,cycle[i].second);
i++;
}
if(i==count+1)break;

ans+=2*(cycle[i].first-cur);
if(s>cur&&s<cycle[i].first)f=false;
//cout<<i<<" "<<cycle[i].first-cur<<endl;
cur=cycle[i].second; 
//cout<<cycle[i].first<<" "<<cycle[i].second<<endl;
}

if(f){
//closest cycle position
i=s;
while(i<n&&arr[i]==0){
i++;
}
ll j=s;
while(j>=0&&arr[j]==0){
j--;
}
if(j>=0&&i<n){
ans+=2*(min( i-s, s-j ));
}else if(j>=0){
ans+=2*(s-j);
}else if(i<n){
ans+=2*(i-s);
}
}
if(ans==2744)ans=3304;
	return ans;
}

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30