Submission #1267985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267985		LaMatematica14	Ancient Books (IOI17_books)	C++20	50 / 100	62 ms	8168 KiB

books

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

long long minimum_walk(vector<int> p, int s) {
    long long ans = 0, N = p.size();
    for (int i=0; i<N; i++) ans += abs(p[i]-i);
    int last_ordered = N, first_unordered = -1;
    for (int i = 0; i < s; i++) {
        if (p[i] != i) break;
        first_unordered = i;
    }
    for (int i = N-1; i > s; i--) {
        if (p[i] != i) break;
        last_ordered = i;
    }
    if (last_ordered == 0) return 0;
    int max_sofar = -1, nseg = 0;
    for(int i = first_unordered+1; i < last_ordered; i++) {
        if (i > max_sofar) nseg++;
        max_sofar = max(max_sofar, p[i]);
    }
    return ans+(nseg-1)*2;
}

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