Submission #622597

#	Time	Username	Problem	Language	Result	Execution time	Memory
622597		KoD	Ancient Books (IOI17_books)	C++17	50 / 100	138 ms	21092 KiB

books

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

using ll = long long;
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);
        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;
        }
    }
    int a = left[s], b = right[s], l = s, r = s;
    const auto add = [&](const int k) {
        a = std::min(a, left[k]);
        b = std::max(b, right[k]);
    };
    while (true) {
        while (a < l or r < b) {
            if (a < l) {
                l -= 1;
                add(l);
            } else {
                r += 1;
                add(r);
            }
        }
        if (0 == l and r == N - 1) {
            break;
        }
        int x = l, xcost = 0, xr = r;
        while (0 < x and xr <= r) {
            x -= 1;
            xcost += 1;
            int k = left[x];
            xr = std::max(xr, right[x]);
            while (k < x) {
                x -= 1;
                k = std::min(k, left[x]);
                xr = std::max(xr, right[x]);
            }
        }
        int y = r, ycost = 0, yl = l;
        while (y < N - 1 and yl >= l) {
            y += 1;
            ycost += 1;
            int k = right[y];
            yl = std::min(yl, left[y]);
            while (y < k) {
                y += 1;
                k = std::max(k, right[y]);
                yl = std::min(yl, left[y]);
            }
        }
        if (right[x] <= r) {
            ans += 2 * (xcost + ycost);
            break;
        }
        if (xcost < ycost) {
            ans += 2 * xcost;
            add(xr);
        } else {
            ans += 2 * ycost;
            add(yl);
        }
    }
    return ans;
}

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