Submission #620021

#	Time	Username	Problem	Language	Result	Execution time	Memory
620021		Ozy	Ancient Books (IOI17_books)	C++17	50 / 100	185 ms	23768 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 1000000

lli n,ini,fin,res,last,activos,a,act,dis;
lli vis[MAX+2];
vector<pair<lli,lli> > eventos;

long long minimum_walk(std::vector<int> p, int s) {

    n = p.size();
    res = 0;

    dis = n+n;
    rep(i,s,n-1) {
        if (p[i] != i) {
            a = i-s;
            dis = min(dis,a);
        }
    }
    repa(i,s,0) {
        if (p[i] != i) {
            a = s-i;
            dis = min(dis,a);
        }
    }
    if (dis == n+n) return 0;

    rep(i,0,n-1) {
        if (vis[i]) continue;
        if (p[i] == i) continue;
        vis[i] = 1;

        ini = i;
        fin = i;
        act = p[i];
        res += abs(i - act);

        while (act != i) {
            vis[act] = 1;
            ini = min(ini,act);
            fin = max(fin,act);
            res += abs(p[act] - act);
            act = p[act];
        }
        eventos.push_back({ini,0});
        eventos.push_back({fin,1});
    }
    sort(eventos.begin(), eventos.end());

    if (eventos.empty()) return res;

    last = eventos[0].first;
    activos = 0;
    for (auto e : eventos) {

        if (activos == 0) {
            a = e.first - last;
            a *= 2;
            res += a;
        }

        last = e.first;
        if (e.second) activos--;
        else activos++;
    }

    res += dis*2;
    return res;
}

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