Cod sursa(job #1934767)

Utilizator 1475369147896537415369Andrei Udriste 1475369147896537415369 Data 21 martie 2017 19:58:54
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <cstdio>

int N, input[10001];
int aux[10001];
char ch;

long long Merge(int sequence[], int left, int right){

    long long inversions = 0;
    int middle = (left + right) / 2;
    int i = left;
    int j = middle + 1;
    int k = left;

    while(i <= middle && j <= right){

        if(sequence[i] <= sequence[j]){
            aux[k++] = sequence[i++];
        }else{
            aux[k++] = sequence[j++];
            inversions += middle - i + 1;
        }
    }

    while(i <= middle){
        aux[k++] = sequence[i++];
    }
    while(j <= right){
        aux[k++] = sequence[j++];
    }
    for(k = left; k <= right; k++){
        sequence[k] = aux[k];
    }

    return inversions;
}

long long Sort(int sequence[], int left, int right){

    long long inversions = 0;

    if(left < right){

        int middle = (left + right) / 2;

        inversions += Sort(sequence, left, middle);
        inversions += Sort(sequence, middle + 1, right);
        inversions += Merge(sequence, left, right);
    }
    return inversions;
}

int main(){

    freopen("litere.in", "r", stdin);
    freopen("litere.out", "w", stdout);

    scanf("%d", &N); getchar();

    for(int i = 1; i <= N; i++){
        ch = getchar();
        input[i] = ch;
    }

    printf("%d", Sort(input, 1, N));

    return 0;
}