Submission #835348

#	Time	Username	Problem	Language	Result	Execution time	Memory
835348		jasmin	Ancient Books (IOI17_books)	C++17	50 / 100	102 ms	10432 KiB

books

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

const int INF=1e9+7;

long long minimum_walk(vector<int> p, int s) {
    int n=p.size();
	
    long long ans=0;
    
    vector<bool> vis(n, false);
    vector<pair<int,int> > ranges;
    for(int i=0; i<n; i++){
        if(vis[i]) continue;

        int v=i;
        int cnt=0;
        int l=i;
        int r=i;
        while(!vis[v]){
            vis[v]=true;

            cnt++;
            l=min(l, v);
            r=max(r, v);

            ans += abs(p[v]-v);
            v=p[v];
        }

        if(cnt!=1){
            ranges.push_back({l, r});
        }
    }
    ranges.push_back({0, 0});
    sort(ranges.begin(), ranges.end());

    int last=0;
    for(auto [l, r]: ranges){

        if(last < l){
            ans += 2*(l-last);
        }

        last=max(last, r);
    }

    return ans;
}

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