Submission #622634

#	Time	Username	Problem	Language	Result	Execution time	Memory
622634		KoD	Ancient Books (IOI17_books)	C++17	100 / 100	152 ms	23788 KiB

books

#include "books.h"
#include <bits/stdc++.h>

using ll = long long;
using std::pair;
using std::vector;

ll minimum_walk(vector<int> P, int s) {
    {
        int l = 0, r = (int)P.size() - 1;
        while (l < s and P[l] == l) {
            l += 1;
        }
        while (r > s and P[r] == r) {
            r -= 1;
        }
        P.erase(P.begin() + r + 1, P.end());
        P.erase(P.begin(), P.begin() + l);
        for (auto& x : P) {
            x -= l;
        }
        s -= l;
    }
    const int N = (int)P.size();
    vector<char> seen(N);
    vector<int> left(N), right(N);
    ll ans = 0;
    for (int i = 0; i < N; ++i) {
        ans += std::abs(P[i] - i);
        if (seen[i]) {
            continue;
        }
        vector<int> cycle;
        for (int j = i; !seen[j]; j = P[j]) {
            seen[j] = true;
            cycle.push_back(j);
        }
        const int l = *std::min_element(cycle.begin(), cycle.end());
        const int r = *std::max_element(cycle.begin(), cycle.end());
        for (const int j : cycle) {
            left[j] = l;
            right[j] = r;
        }
    }
    const auto extend = [&](int& l, int& r) {
        int a = std::min(left[l], left[r]), b = std::max(right[l], right[r]);
        while (a < l or r < b) {
            if (a < l) {
                l -= 1;
                a = std::min(a, left[l]);
                b = std::max(b, right[l]);
            } else {
                r += 1;
                a = std::min(a, left[r]);
                b = std::max(b, right[r]);
            }
        }
    };
    int l = s, r = s;
    while (true) {
        extend(l, r);
        int xl = l, xr = r, xc = 0;
        while (0 < xl and xr <= r) {
            xl -= 1;
            xc += 2;
            extend(xl, xr);
        }
        int yl = l, yr = r, yc = 0;
        while (l <= yl and yr < N - 1) {
            yr += 1;
            yc += 2;
            extend(yl, yr);
        }
        assert(!((xr > r) ^ (yl < l)));
        if (xr <= r) {
            ans += xc + yc;
            break;
        }
        ans += std::min(xc, yc);
        l = std::min(xl, yl);
        r = std::max(xr, yr);
    }
    return ans;
}

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