Submission #423954

#	Time	Username	Problem	Language	Result	Execution time	Memory
423954		timmyfeng	Ancient Books (IOI17_books)	C++17	50 / 100	181 ms	15180 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) {
        	++cycles[left], --cycles[right];
            low = min(low, left), high = max(high, right);
        }
    }

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

    return ans;
}

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