Submission #893212

#	Time	Username	Problem	Language	Result	Execution time	Memory
893212		vjudge1	Ancient Books (IOI17_books)	C++17	50 / 100	108 ms	16080 KiB

books

#include "books.h"

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using ii = pair<int, int>;

struct UF {
    vi e;
    UF(int N) : e(N, -1) {}
    int repr(int u) {
        while(e[u] >= 0) u = e[u];
        return u;
    }

    int join(int u, int v) {
        u = repr(u);
        v = repr(v);
        if(u == v) return 0;
        if(e[u] >= e[v]) swap(u, v);
        e[u] += e[v];
        e[v] = u;
        return 1;
    }
};

long long minimum_walk(vi p, int s) {
    int n = p.size();
    vi on(n, 0), sum(n, 0);
    int mi = n, ma = 0;
    for(int i = 0; i < n; ++i) {
        int st = min(i, p[i]);
        int dr = max(i, p[i]);
        ++sum[st];
        --sum[dr];
        if(st != dr) {
            ma = max(ma, dr);
            mi = min(mi, st);
        }
    }
    for(int i = 1; i < n; ++i)
        sum[i] += sum[i - 1];
    ll re = 0;
    for(int i = 0; i < n; ++i) 
        re += abs(i - p[i]);
    for(int i = s - 1; i >= mi; --i) {
        if(!sum[i]) re += 2;
    }
    for(int i = s; i < ma; ++i)
        if(!sum[i]) re += 2;
    return re;
}

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