Cod sursa(job #3172727)

Utilizator apoputoaievladVlad Cristian Apoputoaie apoputoaievlad Data 21 noiembrie 2023 09:43:32
Problema Litere Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;
int n,a[1000],b[1000];
long long nr;
ifstream fin("litere.in");
ofstream fout("litere.out");
/// interclaseaza secventele a[st..m]
/// cu a[m+1..dr]
void Intercl(int st, int m, int dr)
{
    int i, j, k;
    k = st;
    i = st; j = m+1;
    while (i <= m && j <= dr)
        if (a[i] > a[j])
            {
                b[k++] = a[j++];
                    nr+=m-i+1;
            }
        else b[k++] = a[i++];

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

    /// transfer din b in apoi in a
    for (i = st; i <= dr; i++)
        a[i] = b[i];
}

void MergeSort(int st, int dr)
{
    if (dr - st >= 1)

    {
        int m = (st + dr) / 2;
        MergeSort(st, m);
        MergeSort(m+1, dr);
        Intercl(st, m, dr);
    }
}
int main()
{
    int i;
    char x;
    fin>>n;
    for(i=1;i<=n;i++)
        {
            fin>>x;
            a[i]=x-'a'+1;
        }
    MergeSort(1,n);
    fout<<nr;
    return 0;
}