Submission #684058

#	Time	Username	Problem	Language	Result	Execution time	Memory
684058		piOOE	Ancient Books (IOI17_books)	C++17	100 / 100	202 ms	30744 KiB

books

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

using namespace std;
using ll = long long;

long long minimum_walk(std::vector<int> p, int s) {
    if (is_sorted(p.begin(), p.end())) {
        return 0;
    }

    int n = p.size();

    ll ans = 0;

    vector<int> inv(n);
    for (int i = 0; i < n; ++i) {
        inv[p[i]] = i;

        ans += abs(p[i] - i);
    }

    vector<int> lx(n, -1), rx(n, -1);
    for (int i = 0; i < n; ++i) {
        if (lx[i] == -1) {
            int v = i, mn = n, mx = 0;

            vector<int> cycle;
            do {
                mn = min(mn, v);
                mx = max(mx, v);

                lx[v] = 228;
                cycle.push_back(v);

                v = p[v];
            } while (lx[v] == -1);

            for (int x: cycle) {
                lx[x] = mn, rx[x] = mx;
            }
        }
    }

    auto extend = [&](int &l, int &r, int limL, int limR) {
        int mn = l, mx = r;
        for (int i = l; i <= limL; ++i) {
            mn = min(mn, lx[i]);
            mx = max(mx, rx[i]);
        }
        for (int i = limR; i <= r; ++i) {
            mn = min(mn, lx[i]);
            mx = max(mx, rx[i]);
        }
        l = mn, r = mx;
    };

    int trivL = 0, trivR = n - 1;
    while (p[trivL] == trivL) {
        trivL += 1;
    }
    while (p[trivR] == trivR) {
        trivR -= 1;
    }

    int l = lx[s], r = rx[s];
    extend(l, r, s, s);
    while (l >= 0 && r < n) {
        int cl = l, cr = r;

        int ansL = 0, ansR = 0;
        int mn = n;

        bool found = false;
        while (cl > 0) {
            cl -= 1;
            if (mn > cl) {
                ansL += 1;
            }
            mn = min(mn, p[cl]);
            if (rx[cl] > r) {
                found = true;
                break;
            }
        }

        int mx = 0;

        while (cr < n - 1) {
            cr += 1;
            if (mx < cr) {
                ansR += 1;
            }
            mx = max(mx, p[cr]);
            if (lx[cr] < l) {
                found = true;
                break;
            }
        }

        if (!found) {
            if (trivL < l) {
                ans += (ansL - trivL) * 2;
            }
            if (trivR > r) {
                ans += (ansR - (n - trivR - 1)) * 2;
            }
            break;
        }

        ans += min(ansL, ansR) * 2;
        int pl = l, pr = r;
        l = min(lx[cl], lx[cr]);
        r = max(rx[cr], rx[cr]);
        extend(l, r, pl, pr);
    }

    return ans;
}

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