5733 2023. 09. 10 17:37:58 kukkerman Legmesszebbi rossz sorrendű (35 pont) cpp14 Elfogadva 35/35 54ms 8048 KiB
#include <iostream>
#include <vector>

std::vector<int> beolvas(std::istream &in) {
    size_t n;
    in >> n;

    std::vector<int> v(n);
    for (auto i = 0u; i < n; i++) {
        in >> v[i];
    }

    return v;
}

size_t merge_sort(size_t kezd, size_t veg, std::vector<size_t> &honnan, std::vector<size_t> &hova, const std::vector<int> &v) {
    size_t max_tav = 0u;

    if (veg - kezd > 1) {
        const auto kozep = kezd + (veg - kezd) / 2;
        const auto bal_max_tav = merge_sort(kezd, kozep, hova, honnan, v);
        const auto jobb_max_tav = merge_sort(kozep, veg, hova, honnan, v);
        max_tav = std::max(bal_max_tav, jobb_max_tav);

        size_t bal = kezd;
        size_t jobb = kozep;
        size_t cel = kezd;
        size_t jobb_max_index = 0;
        while (bal < kozep || jobb < veg) {
            if (bal < kozep && (jobb == veg || v[honnan[bal]] <= v[honnan[jobb]])) {
                if (jobb > kozep && max_tav < jobb_max_index - honnan[bal]) {
                    max_tav = jobb_max_index - honnan[bal];
                }
                hova[cel++] = honnan[bal++];

            } else {
                jobb_max_index = std::max(jobb_max_index, honnan[jobb]);
                hova[cel++] = honnan[jobb++];
            }
        }
    }

    return max_tav;
}

void feldolgoz(const std::vector<int> &v) {
    const auto n = v.size();

    std::vector<size_t> honnan(n), hova(n);
    for (auto i = 0u; i < n; i++) {
        honnan[i] = hova[i] = i;
    }

    const auto max_tav = merge_sort(0, n, honnan, hova, v);
    if (max_tav > 0) {
        for (auto i = 0u; i < n; i++) {
            if (v[i] > v[i + max_tav]) {
                std::cout << i + 1 << ' ' << i + 1 + max_tav;
                break;
            }
        }

    } else {
        std::cout << -1;
    }

    std::cout << std::endl;
}

int main() {
    const auto v = beolvas(std::cin);
    feldolgoz(v);

    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 35/35
1 Elfogadva 0/0 3ms 1812 KiB
2 Elfogadva 0/0 54ms 6008 KiB
3 Elfogadva 1/1 3ms 2268 KiB
4 Elfogadva 1/1 3ms 2360 KiB
5 Elfogadva 1/1 3ms 2528 KiB
6 Elfogadva 1/1 2ms 2612 KiB
7 Elfogadva 1/1 2ms 2612 KiB
8 Elfogadva 1/1 3ms 2780 KiB
9 Elfogadva 1/1 3ms 3084 KiB
10 Elfogadva 1/1 4ms 3208 KiB
11 Elfogadva 1/1 4ms 3184 KiB
12 Elfogadva 2/2 20ms 4456 KiB
13 Elfogadva 2/2 24ms 4976 KiB
14 Elfogadva 2/2 25ms 5060 KiB
15 Elfogadva 2/2 16ms 4476 KiB
16 Elfogadva 2/2 26ms 5588 KiB
17 Elfogadva 2/2 39ms 6192 KiB
18 Elfogadva 2/2 43ms 6716 KiB
19 Elfogadva 2/2 48ms 7116 KiB
20 Elfogadva 2/2 50ms 7152 KiB
21 Elfogadva 2/2 54ms 7672 KiB
22 Elfogadva 2/2 54ms 7944 KiB
23 Elfogadva 2/2 39ms 8048 KiB
24 Elfogadva 2/2 41ms 7976 KiB