oj.uz

Submission #677695

# Submission time Handle Problem Language Result Execution time Memory
677695 2023-01-04T07:43:59 Z bashkort Ancient Books (IOI17_books) C++17
0 / 100
 1 ms 280 KB 
#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();

    ll ans = 0;

    vector<int> inv(n);
    for (int i = 0; i < n; ++i) {
        inv[p[i]] = i;

        ans += abs(p[i] - i);
    }

    vector<int> lx(n, -1), rx(n, -1);
    for (int i = 0; i < n; ++i) {
        if (lx[p[i]] == -1) {
            int v = p[i], mn = n, mx = 0;

            vector<int> cycle;
            do {
                mn = min(mn, inv[p[i]]);
                mx = max(mx, inv[p[i]]);

                lx[v] = 228;
                cycle.push_back(v);

                v = p[v];
            } while (lx[v] == -1);

            for (int x: cycle) {
                lx[x] = mn, rx[x] = mx;
            }
        }
    }

    int trivL = 0, trivR = n - 1;
    while (p[trivL] == trivL) {
        trivL += 1;
    }
    while (p[trivR] == trivR) {
        trivR -= 1;
    }

    int l = lx[s], r = rx[s];
    while (l >= 0 && r < n) {
        int cl = l, cr = r;

        int ansL = 0, ansR = 0;
        int mn = n;

        bool found = false;
        while (cl > 0) {
            cl -= 1;
            if (mn > cl) {
                ansL += 1;
            }
            mn = min(mn, p[cl]);
            if (rx[cl] > r) {
                found = true;
                break;
            }
        }

        int mx = 0;

        while (cr < n - 1) {
            cr += 1;
            if (mx < cr) {
                ansR += 1;
            }
            mx = max(mx, p[cr]);
            if (lx[cr] < l) {
                found = true;
                break;
            }
        }

        if (!found) {
            if (trivL < l) {
                ans += (ansL - trivL) * 2;
            }
            if (trivR > r) {
                ans += (ansR - (n - trivR - 1)) * 2;
            }
            break;
        }

        ans += min(ansL, ansR);
        l = min(lx[cl], lx[cr]);
        r = max(rx[cr], rx[cr]);
    }

    return ans;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 280 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 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 280 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 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 280 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 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 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '3304', found: '3513'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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