Submission #835521

#	Time	Username	Problem	Language	Result	Execution time	Memory
835521		jasmin	Ancient Books (IOI17_books)	C++17	0 / 100	1 ms	340 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;
    vector<bool> ends(n);
    vector<bool> starts(n);
    vector<int> cycle(n);
    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;
            cycle[v] = i;
 
            cnt++;
            l=min(l, v);
            r=max(r, v);
 
            ans += abs(p[v]-v);
            v=p[v];
        }
        ends[r] = true;
        starts[l] = true;
 
        if(cnt!=1){
            ranges.push_back({l, r});
        }
    }
    ranges.push_back({s, s});
    sort(ranges.begin(), ranges.end());

    if(ranges.empty()){
        return 0;
    }
 
    int last=ranges[0].first;
    for(auto [l, r]: ranges){
 
        if(last < l){
            ans += 2*(l-last);
        }
 
        last=max(last, r);
    }

    //start: 
    int left=INF;
    int right=-1; int rightborder=-1;
    for(auto [l, r]: ranges){
        if(r<s || s<l) continue;

        left = min(left, l);
        if(rightborder < r){
            rightborder = r;
            right = l;
        }
    }

    set<int> active;
    set<int> reachl;
    for(int i=0; i<n; i++){

        if(starts[i]){
            active.insert(cycle[i]);
        }
        if(ends[i]){
            active.erase(cycle[i]);
        }

        if(cycle[i]==left){
            for(auto e: active){
                reachl.insert(e);
                active.erase(e);
            }
        }

    }
    active.clear();
    set<int> reachr;
    for(int i=0; i<n; i++){

        if(starts[i]){
            active.insert(cycle[i]);
        }
        if(ends[i]){
            active.erase(cycle[i]);
        }

        if(cycle[i]==right){
            for(auto e: active){
                reachr.insert(e);
                active.erase(e);
            }
        }

    }

    vector<bool> good(n);
    if(reachl.find(right)!=reachl.end()){

        for(auto e: reachr){
            good[e]=true;
        }

    }
    if(reachr.find(left)!=reachr.end()){

        for(auto e: reachl){
            good[e]=true;
        }
    }

    int mindist=INF;
    for(int i=0; i<n; i++){

        if(good[cycle[i]]){
            mindist = min(mindist, abs(s-i));
        }
    }
    ans += 2*mindist;
 
    return ans;
}

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