Cod sursa(job #2342844)

Utilizator iustin948Homoranu Iustin iustin948 Data 13 februarie 2019 13:38:36
Problema Litere Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <cstring>
#include <algorithm>

using namespace std;

char a[10005], b[10005];
int n, cnt;

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

int Int(int st, int m, int dr)
{
    int i, j, k;
    i = st; j = m + 1; k = 0;
    while(i <= m && j <= dr)
        if(a[i] <= a[j])b[++k] = a[i++];
        else
        {
            cnt += (m - i + 1);
            b[++k] = a[j++];
        }

    while(i <= m)
        b[++k] = a[i++];
    while(j <= dr)
        b[++k] = a[j++];

    j = 1;
    for(i = st; i <= dr; i++)
        a[i] = b[j++];

}

void MSort(int st, int dr)
{
    if(dr - st <= 1)
    {
        if(a[st] > a[dr])
        {
            cnt++;
            swap(a[st], a[dr]);
        }
    }
    else
    {
        int m = (st + dr) / 2;
        MSort(st, m);
        MSort(m + 1, dr);
        Int(st, m, dr);
    }
}

int main()
{
    fin >> n;
    fin.getline(a+1,10005);

    MSort(1, n);
    fout << cnt << "\n";

    return 0;
}