Submission #119673

#	Time	Username	Problem	Language	Result	Execution time	Memory
119673		thebes	Ancient Books (IOI17_books)	C++14	50 / 100	295 ms	46264 KiB

books

#include <bits/stdc++.h>
using namespace std;

const int MN = 1e6+6;
typedef long long ll;
ll n, i, arr[MN], id[MN], j, ans, nxt, l[MN], r[MN], L, R, ord[MN], sz;

void dfs(ll n){
    ans += abs(arr[n]-n);
    l[id[n]]=min(l[id[n]],n);
    r[id[n]]=max(r[id[n]],n);
    if(id[arr[n]]) return;
    id[arr[n]] = id[n];
    dfs(arr[n]);
}

ll minimum_walk(vector<int> p, int s){
    n = p.size();
    if(s) return 0; // rip
    for(i=0;i<n;i++) arr[i+1]=p[i]+1;
    for(i=1;i<=n;i++) l[i]=n+1;
    for(i=1;i<=n;i++) if(!id[i]) id[i]=++nxt, dfs(i);
    for(i=1;i<=nxt;i++){
        if(l[i]!=r[i]){
            ord[++sz] = i;
        }
    }
    sort(ord+1,ord+sz+1,[](ll i,ll j){return l[i]<l[j];});
    R = 1;
    for(i=1;i<=sz;i++){
        ans += 2*max(0LL,l[ord[i]]-R);
        R = max(R, r[ord[i]]);
    }
    return ans;
}

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