Cod sursa(job #2784482)

Utilizator claudiu.gatinaFMI Claudiu Gatina claudiu.gatina Data 16 octombrie 2021 15:53:49
Problema Litere Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
#include <cstdlib>
#include <string>
#include <iostream>

using namespace std;

const int NMAX = 10000;

int charCount[256];
int charBegin[256];
int total = 0;
char s[NMAX];
char aux[NMAX];

void mergeSort(int l, int r)
{
    if(l == r) {
        return;
    }
    int m = (l + r) / 2;
    mergeSort(l, m);
    mergeSort(m + 1, r);

    int k = l;
    int j = m + 1;

    for(int i = l; i <= m; ++i) {
        while(j <= r && s[j] < s[i]) {
            total += (m - i + 1);
            aux[k++] = s[j++];
        }
        aux[k++] = s[i];
    }

    while(j <= r) {
        aux[k++] = s[j++];
    }

    for(int i = l; i <= r; ++i) {
        s[i] = aux[i];
    }
}

int main()
{
    fstream fin("litere.in", ios::in);
    fstream fout("litere.out", ios::out);

    int n;
    fin >> n;
    fin >> s;

    mergeSort(0, n - 1);

    fout << total;

    return 0;
}