Cod sursa(job #2426820)

Utilizator sygAndreiIonitaIonita Andrei sygAndreiIonita Data 29 mai 2019 15:49:29
Problema Litere Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>

using namespace std;

ifstream in ("litere.in");
ofstream out ("litere.out");

int arr[10001];

int merge(int arr[], int temp[], int left, int mid, int right)
{
    int inv_count = 0;

    int i = left;
    int j = mid;
    int k = left;
    while ((i <= mid - 1) && (j <= right))
    {
        if (arr[i] <= arr[j])
            temp[k++] = arr[i++];
        else
        {
            temp[k++] = arr[j++];
            inv_count = inv_count + (mid - i);
        }
    }
    while (i <= mid - 1)
        temp[k++] = arr[i++];
    while (j <= right)
        temp[k++] = arr[j++];
    for (i=left; i <= right; i++)
        arr[i] = temp[i];

    return inv_count;
}
int _mergeSort(int arr[], int temp[], int left, int right)
{
    int mid,inv_count = 0;
    if (right > left)
    {
        mid = (right + left)/2;
        inv_count  = _mergeSort(arr, temp, left, mid);
        inv_count += _mergeSort(arr, temp, mid+1, right);
        inv_count += merge(arr, temp, left, mid+1, right);
    }

    return inv_count;
}
int countSwaps(int arr[], int n)
{
    int temp[n];
    return _mergeSort(arr, temp, 0, n - 1);
}

int main(int argv, char** args)
{
    int n,i;
    char c;
    in>>n;
    for (i=0;i<n;i++)
        in>>c,arr[i]=(int)c;
    out<<countSwaps(arr,n);
    return 0;
}