Cod sursa(job #2768460)

Utilizator DragosC1Dragos DragosC1 Data 10 august 2021 20:38:06
Problema Litere Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <fstream>
#include <iostream>
using namespace std;

int n;
int a[10001];

void read() {
    int i;
    char ch;
    ifstream f("litere.in");
    f >> n;
    for (i = 1; i <= n; i++) {
        f >> ch;
        a[i] = ch - 'a';
    }
    f.close();
}

int nr;
int aux[10001];

void merge_sort(int st, int dr) {
    if (st == dr)
        return;
    else {
        int mij = (st + dr) / 2;
        merge_sort(st, mij);
        merge_sort(mij + 1, dr);
        int i, j, k = 0;
        i = st, j = mij + 1;
        while (i <= mij && j <= dr) {
            if (a[i] <= a[j]) 
                aux[++k] = a[i++];
            else {
                nr += (j - (k + st));
                aux[++k] = a[j++];
            }
        }
        while (i <= mij)
            aux[++k] = a[i++];
        while (j <= dr) 
            aux[++k] = a[j++];
        for (k = 0, i = st; i <= dr; i++)
            a[i] = aux[++k];
    }
}

void output() {
    ofstream g("litere.out");
    g << nr;
    g.close();
}

int main() {
    read();
    int i;
    merge_sort(1, n);
    output();
    return 0;
}