Submission #642103

#	Time	Username	Problem	Language	Result	Execution time	Memory
642103		piOOE	Ancient Books (IOI17_books)	C++17	50 / 100	130 ms	18764 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();
    vector<int> inv(n);
    for (int i = 0; i < n; ++i) {
        inv[p[i]] = i;
    }
    ll ans = 0;
    for (int j = 0; j < n; ++j) {
        ans += abs(p[j] - inv[p[j]]);
    }
    int L = 0, R = n;
    while (p[L] == L) ++L;
    while (p[R - 1] == R - 1) --R;
    if (s < L || s >= R) {
        int i = 0;
        int mx = -1;
        for (; i < n; ++i) {
            if (is_sorted(p.begin() + i, p.end())) break;
            if (i && mx < i) {
                ans += 2;
            }
            mx = max(mx, p[i]);
        }
        return ans;
    } else {
        int mn = n;
        for (int j = s; j < R; ++j) mn = min(mn, p[j]);
        for (int j = s - 1; j >= L; --j) {
            if (j < mn) {
                ans += 2;
            }
            mn = min(mn, p[j]);
        }
        int mx = -1;
        for (int j = L; j <= s; ++j) {
            mx = max(mx, p[j]);
        }
        for (int j = s + 1; j < R; ++j) {
            if (j > mx) ans += 2;
            mx = max(mx, p[j]);
        }
        return ans;
    }
}

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