Submission #425918

#	Time	Username	Problem	Language	Result	Execution time	Memory
425918		2fat2code	Ancient Books (IOI17_books)	C++17	100 / 100	350 ms	76564 KiB

books

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

const int nmax = 1000005;

long long n, comp, l_ned, r_ned, ans, viz[nmax];
vector<long long>cicles[nmax];

void extend(LL &l, LL &r, LL &ll, LL &rr){
    while(l > ll || r < rr){
        if(l > ll){
            --l;
            ll = min(ll, cicles[viz[l]][0]);
            rr = max(rr, cicles[viz[l]].back());
        }
        if(r < rr){
            ++r;
            ll = min(ll, cicles[viz[r]][0]);
            rr = max(rr, cicles[viz[r]].back());
        }
    }
}

void compute(int s){
    LL l = s, r = s, ll = cicles[viz[s]][0], rr = cicles[viz[s]].back();
    extend(l, r, ll, rr);
    while(ll > 0 || rr < n - 1){
        LL calcright = 0, maxi = -1, findright = 0;
        for(int i=rr+1;i<=n-1;i++){
            if(i > maxi){
                calcright += 2LL;
            }
            maxi = max(maxi, cicles[viz[i]].back());
            if(cicles[viz[i]][0] < ll){
                findright = viz[i];
                break;
            }
        }
        if(!findright){
            rr = n - 1;
            ans += calcright;
        }
        LL calcleft = 0, mini = n, findleft = 0;
        for(int i=ll-1;i>=0;i--){
            if(i < mini){
                calcleft += 2LL;
            }
            mini = min(mini, cicles[viz[i]][0]);
            if(cicles[viz[i]].back() > rr){
                findleft = viz[i];
                break;
            }
        }
        if(!findleft){
            ll = 0;
            ans += calcleft;
        }
        else{
            ans += min(calcleft, calcright);
            if(calcleft > calcright){
                ll = min(ll, cicles[findright][0]);
                rr = max(rr, cicles[findright].back());
            }
            else{
                ll = min(ll, cicles[findleft][0]);
                rr = max(rr, cicles[findleft].back());
            }
        }
        extend(l, r, ll, rr);
    }
}

long long minimum_walk(vector<int> p, int s) {
    n = (int)p.size();
	while(p[l_ned] == l_ned && s > l_ned) l_ned++;
	r_ned = n - 1;
	while(p[r_ned] == r_ned && s < r_ned) r_ned--;
	vector<int>aux;
	for(int i=l_ned;i<=r_ned;i++){
        aux.push_back(p[i] - l_ned);
	}
	swap(aux, p);
	s -= l_ned;
	n = (int)p.size();

	for(int i=0;i<n;i++){
        ans += abs(i - p[i]);
	}
	for(int i=0;i<n;i++){
        if(!viz[i]){
            ++comp;
            viz[i] = comp;
            cicles[comp].push_back(i);
            int curr = p[i];
            while(curr  !=  i){
                viz[curr] = comp;
                cicles[comp].push_back(curr);
                curr = p[curr];
            }
        }
	}
	for(int i=1;i<=comp;i++){
        sort(all(cicles[i]));
	}
	compute(s);
    return ans;
}

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