Submission #835895

#	Time	Username	Problem	Language	Result	Execution time	Memory
835895		jasmin	Ancient Books (IOI17_books)	C++17	50 / 100	281 ms	50252 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<bool> ends(n);
    vector<bool> starts(n);
    vector<int> cycle(n);
    set<pair<int,int> > ranges;
    for(int i=0; i<n; i++){
        if(vis[i]) continue;
 
        int v=i;
        int l=i;
        int r=i;
        int cnt=0;
        while(!vis[v]){
            vis[v]=true;
            cycle[v] = i;
 
            l=min(l, v);
            r=max(r, v);
            cnt++;
 
            ans += abs(p[v]-v);
            v=p[v];
        }
        ends[r] = true;
        starts[l] = true;
 
        if(cnt!=1 || i==s){
            ranges.insert({l, r});
        }
    }

    //start: 
    set<int> free;
    set<int> active;
    for(auto [l, r]: ranges){

        auto it=active.upper_bound(r);
        if(it==active.end()){

            free.insert(l);
            free.insert(r);

            active.insert(r);
        }
    }
    free.insert(s);

    int l=s; int r=s;
    vector<int> queue; queue.push_back(s);
    vis.assign(n, false);
    while(!free.empty()){

        if(!queue.empty()){
            int cur=queue.back();
            queue.pop_back();

            while(!vis[cur]){
                vis[cur]=true;
                free.erase(cur);

                l=min(l, cur);
                r=max(r, cur);

                cur = p[cur];
            }

            vector<int> neu;
            auto it=free.upper_bound(l);
            while(it!=free.end() && *it<r){

                neu.push_back(*it);
                it=next(it);
            }
            for(auto e: neu){
                queue.push_back(e);
                free.erase(e);
            }

        }
        else{

            auto itleft = free.upper_bound(l);
            int left=-1; int distleft=INF;
            if(itleft!=free.begin()){

                left = *prev(itleft);
                distleft = l-left;

            }
            
            auto itright = free.upper_bound(r);
            int right=-1; int distright = INF;
            if(itright!=free.end()){

                right = *itright;
                distright = right -r;
            }


            if((distleft <= distright || right==-1) && left!=-1){

                ans += 2*distleft;
                free.erase(left);
                queue.push_back(left);
            }
            else if(right!=-1){

                ans += 2*distright;
                free.erase(right);
                queue.push_back(right);
            }

        }

    }

    return ans;
}

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