Cod sursa(job #3277266)

Utilizator Gergo123Schradi Gergo Gergo123 Data 15 februarie 2025 15:43:52
Problema Litere Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>

using namespace std;

// Funcția care îmbină cele două jumătăți și numără inversiunile
long long mergeAndCount(vector<char>& arr, vector<char>& temp, int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    long long invCount = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            invCount += (mid - i + 1);  // Toate elementele rămase în stânga sunt inversiuni
        }
    }

    // Copiem restul elementelor din stânga (dacă există)
    while (i <= mid) temp[k++] = arr[i++];

    // Copiem restul elementelor din dreapta (dacă există)
    while (j <= right) temp[k++] = arr[j++];

    // Copiem înapoi elementele sortate în array-ul original
    for (i = left; i <= right; i++) arr[i] = temp[i];

    return invCount;
}

// Funcția recursivă Merge Sort care sortează și numără inversiunile
long long mergeSortAndCount(vector<char>& arr, vector<char>& temp, int left, int right) {
    if (left >= right) return 0;

    int mid = (left + right) / 2;
    long long invCount = 0;

    invCount += mergeSortAndCount(arr, temp, left, mid);      // Sortăm și numărăm în stânga
    invCount += mergeSortAndCount(arr, temp, mid + 1, right); // Sortăm și numărăm în dreapta
    invCount += mergeAndCount(arr, temp, left, mid, right);   // Îmbinăm și numărăm inversiunile între jumătăți

    return invCount;
}

int main() {
    ifstream fin("litere.in");
    ofstream fout("litere.out");

    int N;
    fin >> N;

    vector<char> arr(N);
    for (int i = 0; i < N; i++) fin >> arr[i];

    vector<char> temp(N);
    long long result = mergeSortAndCount(arr, temp, 0, N - 1);

    fout << result << "\n";

    fin.close();
    fout.close();
    return 0;
}