paletta.cpp

#include <algorithm>
#include <vector>

using namespace std;

#include <iostream>
#include <vector>

long long mergeAndCount(std::vector<int>& arr, int left, int mid, int right) {
    std::vector<int> leftArr(arr.begin() + left, arr.begin() + mid + 1);
    std::vector<int> rightArr(arr.begin() + mid + 1, arr.begin() + right + 1);

    int i = 0, j = 0, k = left;
    long long swaps = 0;

    while (i < leftArr.size() && j < rightArr.size()) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k++] = leftArr[i++];
        } else {
            arr[k++] = rightArr[j++];
            swaps += leftArr.size() - i; // elementi rimanenti a sinistra > elemento a destra
        }
    }

    while (i < leftArr.size()) {
        arr[k++] = leftArr[i++];
    }

    while (j < rightArr.size()) {
        arr[k++] = rightArr[j++];
    }

    return swaps;
}

long long mergeSortAndCount(std::vector<int>& arr, int left, int right) {
    long long swaps = 0;

    if (left < right) {
        int mid = left + (right - left) / 2;

        swaps += mergeSortAndCount(arr, left, mid);
        swaps += mergeSortAndCount(arr, mid + 1, right);

        swaps += mergeAndCount(arr, left, mid, right);
    }

    return swaps;
}

long long paletta_sort(int N, int V[]) {
    // vector<int> index(N);
    vector<int> odd (N/2 + N%2);
    vector<int> even (N/2);

    // verifica parità
    for (int i=0; i<N; i++) {
        if (V[i] % 2 != i % 2) return -1;
        // index[V[i]] = i;
        
        if (V[i] % 2) {
            even[i/2] = V[i];
        } else {
            odd[i/2] = V[i];
        }
    }

    long long count = 0;
    
    // sorting
    /*for (int i=0; i<N; i++) {
        long long j = index[i];

        while (j >= i + 2) {
            swap (V[j], V[j-2]);
            swap (index[V[j]], index[V[j-2]]);
            count ++;

            j -= 2;
        }
    }*/

    return mergeSortAndCount(odd, 0, odd.size()-1) + mergeSortAndCount(even, 0, even.size()-1);
}