oj.uz

Submission #622556

# Submission time Handle Problem Language Result Execution time Memory
622556 2022-08-04T11:26:59 Z KoD Ancient Books (IOI17_books) C++17
0 / 100
 1 ms 212 KB 
#include "books.h"
#include <bits/stdc++.h>

using ll = long long;
using std::vector;

ll minimum_walk(vector<int> P, int s) {
    {
        int l = 0, r = (int)P.size() - 1;
        while (l < s and P[l] == l) {
            l += 1;
        }
        while (r > s and P[r] == r) {
            r -= 1;
        }
        P.erase(P.begin() + r + 1, P.end());
        P.erase(P.begin(), P.begin() + l);
        s -= l;
    }
    const int N = (int)P.size();
    ll ans = 0;
    vector<char> seen(N);
    vector<int> left(N), right(N);
    for (int i = 0; i < N; ++i) {
        if (seen[i]) {
            continue;
        }
        vector<int> cycle;
        for (int j = i; !seen[j]; j = P[j]) {
            seen[j] = true;
            cycle.push_back(j);
        }
        const int l = *std::min_element(cycle.begin(), cycle.end());
        const int r = *std::max_element(cycle.begin(), cycle.end());
        for (const int j : cycle) {
            left[j] = l;
            right[j] = r;
        }
        ans += r - l;
    }
    int a = left[s], b = right[s], l = s, r = s;
    const auto add = [&](const int k) {
        a = std::min(a, left[k]);
        b = std::max(b, right[k]);
    };
    while (true) {
        while (a < l or r < b) {
            if (a < l) {
                l -= 1;
                add(l);
            } else {
                r += 1;
                add(r);
            }
        }
        if (0 == l and r == N - 1) {
            break;
        }
        ans += 1;
        if (0 < l and (r == N - 1 or (right[r + 1] - left[r + 1]) < (right[l - 1] - left[l - 1]))) {
            l -= 1;
            add(l);
        } else {
            r += 1;
            add(r);
        }
    }
    return 2 * ans;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '8', found: '6'
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '8', found: '6'
4 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '8', found: '6'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '3304', found: '3482'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '8', found: '6'
4 Halted 0 ms 0 KB -