Submission #992485

#	Time	Username	Problem	Language	Result	Execution time	Memory
992485		bachhoangxuan	Ancient Books (IOI17_books)	C++17	50 / 100	91 ms	16012 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;
    }
    return ans;
}

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