Submission #992691

#	Time	Username	Problem	Language	Result	Execution time	Memory
992691		bachhoangxuan	Ancient Books (IOI17_books)	C++17	50 / 100	118 ms	21528 KiB

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int cnt[maxn],f[maxn];

long long minimum_walk(std::vector<int> p, int s) {
    long long ans=0;
    int n=(int)p.size();
    for(int i=0;i<n;i++){
        if(!f[i] && i!=p[i]){
            int u=i,mn=i,mx=i;
            while(!f[u]){
                f[u]=1;
                mn=min(mn,u);
                mx=max(mx,u);
                u=p[u];
            }
            cnt[mn]++;
            cnt[mx]--;
        }
        ans+=abs(i-p[i]);
    }
    for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1];
    int d=0;
    for(int i=n-1;i>=s;i--){
        if(cnt[i]) d=1;
        else ans+=2*d;
    }
    d=0;
    for(int i=0;i<s;i++){
        if(cnt[i]) d=1;
        else ans+=2*d;
    }
    if(s && cnt[s-1] && s<n-1 && cnt[s] && s==p[s]){
        int l=s,r=s;
        while(l>=0 && l==p[l]) l--;
        while(r<n && r==p[r]) r++;
        ans+=2*(min(s-l,r-s)-1);
    }
    return ans;
}

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