Submission #424383

#	Time	Username	Problem	Language	Result	Execution time	Memory
424383		timmyfeng	Ancient Books (IOI17_books)	C++17	100 / 100	256 ms	27720 KiB

books

#include <bits/stdc++.h>
using namespace std;

const int N = 1000000;

int first[N], last[N], cycles[N];
bool visited[N];

long long minimum_walk(vector<int> perm, int start) {
    int n = perm.size();
    long long ans = 0;

    int low = start, high = start;
    for (int i = 0; i < n; ++i) {
        ans += abs(perm[i] - i);
        if (!visited[i]) {
            int j = i, k = i;
            while (!visited[j]) {
                visited[j] = true;
                k = max(k, j);
                j = perm[j];
            }

            do {
                first[j] = i, last[j] = k;
                j = perm[j];
            } while (j != i);

            if (i != k) {
                low = min(low, i), high = max(high, k);
                ++cycles[i], --cycles[k];
            }
        }
    }

    partial_sum(cycles, cycles + n, cycles);
    ans += 2 * count(cycles + low, cycles + high, 0);

    bool init = false;
    low = high = start;
    while (cycles[high] > 0) {
        int cost_h = 0, ptr_h = high, new_high = high;
        int cost_l = 0, ptr_l = low, new_low = low;

        if (init) {
            while (first[ptr_h] >= low) {
                new_high = max(new_high, last[ptr_h]);
                if (ptr_h == new_high) {
                    cost_h += 2;
                    ++new_high;
                }
                ++ptr_h;
            }

            while (last[ptr_l] <= high) {
                new_low = min(new_low, first[ptr_l]);
                if (ptr_l == new_low) {
                    cost_l += 2;
                    --new_low;
                }
                --ptr_l;
            }
        }

        ans += min(cost_h, cost_l);
        while (new_low <= ptr_l || ptr_h <= new_high) {
            int i = new_low <= ptr_l ? ptr_l-- : ptr_h++;
            new_low = min(new_low, first[i]);
            new_high = max(new_high, last[i]);
        }

        low = new_low, high = new_high, init = true;
    }

    return ans;
}

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