Submission #835887

#	Time	Username	Problem	Language	Result	Execution time	Memory
835887		jasmin	Ancient Books (IOI17_books)	C++17	50 / 100	1229 ms	63804 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 l=i;
        int r=i;
        while(!vis[v]){
            vis[v]=true;
            cycle[v] = i;
 
            l=min(l, v);
            r=max(r, v);
 
            ans += abs(p[v]-v);
            v=p[v];
        }
        ends[r] = true;
        starts[l] = true;
 
    }

    //start: 
    set<int> free;
    for(int i=0; i<n; i++){
        if(p[i]!=i || i==s){
            free.insert(i);
        }
    }

    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 && left!=-1 && starts[left]){

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

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

                if(distleft<= distright && 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