oj.uz

Submission #1006479

# Submission time Handle Problem Language Result Execution time Memory
1006479 2024-06-24T02:32:21 Z thangdz2k7 Ancient Books (IOI17_books) C++17
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

int L = -1, R = -1, p[N], n, l, r;

int g(int &l, int &r){
    int ed = r + 1;
    int st = n + 1;
    int be = r;
    int a = 0;
    while (r <= R && r < ed){
        ++ r;
        if (r == R + 1) break;
        a += 2;
        ed = max(ed, p[r]);
        st = min(st, p[r]);
        if (st < be) break;
    }

    be = l;
    ed = l - 1;
    st = -1;
    int b = 0;
    while (l > ed && l >= L){
        -- l;
        if (l == L - 1) return a + b;
        b += 2;
        ed = min(ed, p[l]);
        st = max(st, p[l]);
        if (st > be) break;
    }

    return min(a, b);
}

long long minimum_walk(vector <int> arr, int s){
    int n = arr.size();
    for (int i = 0; i < n; ++ i) p[i] = arr[i];

    long long ans = 0;
    for (int i = 0; i < n; ++ i){
        ans += abs(p[i] - i);
        if (p[i] != i){
            if (L != -1) L = i;
            R = i;
        }
    }

    l = s;
    r = s;

    while (L <= l && r <= R) ans += g(l, r);

    return ans;
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

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