Submission #422845

#	Time	Username	Problem	Language	Result	Execution time	Memory
422845		2fat2code	Ancient Books (IOI17_books)	C++17	50 / 100	270 ms	63620 KiB

books

#include "books.h"
#include<bits/stdc++.h>
#define fr first
#define sc second
#define all(s) s.begin(), s.end()
using namespace std;

const int nmax = 1000005;

long long n, ans = 0, viz[nmax], comp = 0, cost, diff = 1e18, el = 0;
vector<pair<long long,long long>>ranges;
vector<long long>nod[nmax];

long long minimum_walk(vector<int> p, int s) {
	n = (int)p.size();
	for(int i=0;i<n;i++){
        ans += abs(p[i] - i);
	}
	for(int i=s;i>=0;i--){
        if(p[i] != i){
            if(abs(s-i) < diff){
                diff = abs(i - s);
                el = i;
            }
        }
	}
	for(int i=s;i<n;i++){
        if(p[i] != i){
            if(abs(s-i) < diff){
                diff = abs(i - s);
                el = i;
            }
        }
	}
	s = el;
	if(diff == 1e18) diff = 0;
	for(int i=0;i<n;i++){
        if(!viz[i]){
            int maxi = i, mini = i;
            comp++;
            viz[i] = comp;
            int curr = p[i];
            while(curr != i){
                viz[curr] = comp;
                maxi = max(maxi, curr);
                mini = min(mini, curr);
                curr = p[curr];
            }
            ranges.push_back({mini, maxi});
        }
	}
    while(ranges.size() && ranges.back().fr == ranges.back().sc && ranges.back().sc > s){
        ranges.pop_back();
    }
    reverse(all(ranges));
    while(ranges.size() && ranges.back().fr == ranges.back().sc && ranges.back().sc < s){
        ranges.pop_back();
    }
	sort(all(ranges));
	deque<pair<long long,long long>>Q;
	for(auto it : ranges){
        Q.push_back(it);
	}
	queue<pair<long long, long long>>rn;
	while(Q.size()){
        cost += 2;
        rn.push(Q.front());
        Q.pop_front();
        while(rn.size()){
            auto it = rn.front();
            rn.pop();
            while(Q.size() && Q.front().fr <= it.sc){
                rn.push(Q.front());
                Q.pop_front();
            }
        }
	}
	cost -= 2LL;
	return ans + cost + diff * 2LL;
}

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