57332023-09-10 17:37:58kukkermanLegmesszebbi rossz sorrendű (35 pont)cpp14Accepted 35/3554ms8048 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;
}
SubtaskSumTestVerdictTimeMemory
base35/35
1Accepted0/03ms1812 KiB
2Accepted0/054ms6008 KiB
3Accepted1/13ms2268 KiB
4Accepted1/13ms2360 KiB
5Accepted1/13ms2528 KiB
6Accepted1/12ms2612 KiB
7Accepted1/12ms2612 KiB
8Accepted1/13ms2780 KiB
9Accepted1/13ms3084 KiB
10Accepted1/14ms3208 KiB
11Accepted1/14ms3184 KiB
12Accepted2/220ms4456 KiB
13Accepted2/224ms4976 KiB
14Accepted2/225ms5060 KiB
15Accepted2/216ms4476 KiB
16Accepted2/226ms5588 KiB
17Accepted2/239ms6192 KiB
18Accepted2/243ms6716 KiB
19Accepted2/248ms7116 KiB
20Accepted2/250ms7152 KiB
21Accepted2/254ms7672 KiB
22Accepted2/254ms7944 KiB
23Accepted2/239ms8048 KiB
24Accepted2/241ms7976 KiB