Submission #893210

#	Time	Username	Problem	Language	Result	Execution time	Memory
893210		vjudge1	Ancient Books (IOI17_books)	C++17	22 / 100	2102 ms	17304 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);
    for(int i = 0; i + 1 < n; ++i) {
        int vma = 0, vmi = n;
        for(int j = 0; j <= i; ++j)
            vma = max(vma, p[j]);
        for(int j = i + 1; j < n; ++j)
            vmi = min(vmi, p[j]);
        if(vma > vmi) {
            on[i] = 1;
        } 
    }
    int re = 0;
    for(int i = 0; i < n; ++i) 
        re += abs(i - p[i]);
    for(int i = 0; i < n; ++i) {
        if(!on[i]) {
            for(int j = i + 1; j < n; ++j)
                if(on[j]) {
                    re += 2;
                    break;
                }
        }
    }
    return re;
}

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