Submission #835317

#	Time	Username	Problem	Language	Result	Execution time	Memory
835317		jasmin	Ancient Books (IOI17_books)	C++17	0 / 100	1 ms	468 KiB

books

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

const int INF=1e9+7;

long long minimum_walk(std::vector<int> p, int s) {
    int n=p.size();
	
    long long ans=0;
    
    vector<bool> vis(n, false);
    vector<int> cycle(n, -1);
    vector<int> starts(n, -1); //-1: nothing, 0: starts, 1: ends
    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];
        }

        if(cnt==1 && i!=s){
            cycle[i] = -1;
        }
        starts[l]=0;
        starts[r]=1; 
    }

    
    set<int> active;
    vector<bool> unfinished(n, false);
    set<int> good;
    for(int i=0; i<n; i++){
        if(cycle[i]==-1) continue;
        good.insert(i);

        if(starts[i]==0){
            active.insert(cycle[i]);
        }
        if(starts[i]==2 && active.find(cycle[i])!=active.end()){
            active.erase(cycle[i]);

            unfinished[cycle[i]]=true;
        }

        while(!active.empty() && *active.begin() != cycle[i]){
            active.erase(*active.begin());
        }
        while(!active.empty() && *prev(active.end()) != cycle[i]){
            active.erase(*prev(active.end()));
        }
    }

    vector<int> add(n, INF);
    for(int i=0; i<n; i++){
        if(!unfinished[cycle[i]]) continue;
        assert(unfinished[cycle[i]]);

        int a = INF;
        auto it=good.upper_bound(i);
        if(it!=good.end()){
            a = min(a, 2*(*it - i));
        }
        if(it!=good.begin()){
            a = min(a, 2*(i - *it));
        }
        
        add[cycle[i]] = min(add[cycle[i]], a);
    }

    for(int i=0; i<n; i++){
        if(add[i] != INF){
            ans+=add[i];
        }
    }

    return ans;
}

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