Submission #423964

#	Time	Username	Problem	Language	Result	Execution time	Memory
423964		timmyfeng	Ancient Books (IOI17_books)	C++17	50 / 100	153 ms	12996 KiB

books

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

const int N = 1000000;

bool visited[N];
int cycles[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);

        int left = i, right = i, j = i;
        while (!visited[j]) {
            left = min(left, j), right = max(right, j);
            visited[j] = true;
            j = perm[j];
        }

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

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

    if (cycles[start] > 0) {
        int left = start, right = start;
        while (perm[left] == left) {
            --left;
        }
        while (perm[right] == right) {
            ++right;
        }
        ans += 2 * min(start - left, right - start);
    }

    return ans;
}

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