131472025-01-06 18:31:53zsomborvarszegiInverziócpp17Hibás válasz 3/50284ms4324 KiB
#include <iostream>
#include <vector>
#include <tuple>
using namespace std;

pair<int, pair<int, int>> merge_and_count(vector<int>& arr, vector<int>& temp, int left, int mid, int right) {
    int i = left;
    int j = mid + 1;
    int k = left;
    int max_distance = -1;
    pair<int, int> indices = {-1, -1};

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            if ((j - 1) - i > max_distance) {
                max_distance = (j - 1) - i;
                indices = {i + 1, j};
            }
        }
    }

    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    for (int i = left; i <= right; i++) arr[i] = temp[i];

    return {max_distance, indices};
}

pair<int, pair<int, int>> merge_sort_and_count(vector<int>& arr, vector<int>& temp, int left, int right) {
    if (left >= right) return {-1, {-1, -1}};

    int mid = (left + right) / 2;
    auto left_result = merge_sort_and_count(arr, temp, left, mid);
    auto right_result = merge_sort_and_count(arr, temp, mid + 1, right);
    auto merge_result = merge_and_count(arr, temp, left, mid, right);

    if (left_result.first >= right_result.first && left_result.first >= merge_result.first) {
        return left_result;
    } else if (right_result.first >= left_result.first && right_result.first >= merge_result.first) {
        return right_result;
    } else {
        return merge_result;
    }
}

int main() {
    int n;
    cin >> n;

    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    vector<int> temp(n);
    auto result = merge_sort_and_count(arr, temp, 0, n - 1);

    if (result.first == -1) {
        cout << -1 << endl;
    } else {
        cout << result.second.first << " " << result.second.second << endl;
    }

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base3/50
1Elfogadva0/01ms316 KiB
2Hibás válasz0/020ms564 KiB
3Elfogadva1/11ms316 KiB
4Hibás válasz0/21ms316 KiB
5Hibás válasz0/71ms316 KiB
6Hibás válasz0/225ms616 KiB
7Hibás válasz0/2223ms4152 KiB
8Hibás válasz0/2279ms4160 KiB
9Hibás válasz0/2282ms4156 KiB
10Hibás válasz0/2275ms4156 KiB
11Hibás válasz0/2282ms4148 KiB
12Hibás válasz0/2272ms4148 KiB
13Hibás válasz0/2277ms4156 KiB
14Hibás válasz0/2277ms4148 KiB
15Hibás válasz0/2223ms4148 KiB
16Hibás válasz0/2284ms4148 KiB
17Hibás válasz0/2277ms4324 KiB
18Hibás válasz0/2277ms4148 KiB
19Hibás válasz0/3223ms4160 KiB
20Hibás válasz0/3223ms4144 KiB
21Hibás válasz0/2222ms4148 KiB
22Hibás válasz0/2275ms4148 KiB
23Hibás válasz0/2277ms4164 KiB
24Elfogadva2/2209ms4160 KiB