제출 #423148

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
423148		Pbezz	고대 책들 (IOI17_books)	C++14	50 / 100	213 ms	34372 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;
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);
//cout<<i<<" "<<cycle[i].first-cur<<endl;
cur=cycle[i].second; 
//cout<<cycle[i].first<<" "<<cycle[i].second<<endl;
}

//maxi=0; 
//for(i=1;i<=count;i++){
//maxi=max(maxi,cycle[i].second);
//cout<<cycle[i].first<<" "<<cycle[i].second<<endl;
//}

//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(s>maxi){
ans+=2*(s-maxi);
}else if(s<cycle[1].first){//cout<<"haha "<<cycle[0]
ans+=2*(cycle[1].first-s);
}*/
//adicionar o pedaço do bundle em que o s se insere
	return ans;
}

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