Cod sursa(job #1785683)

Utilizator tanasaradutanasaradu tanasaradu Data 21 octombrie 2016 19:56:08
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("litere.in");
ofstream fout("litere.out");
int n,a[10005],b[10005];
char cuv[10005];
long long cnt;
void Citire()
{
    int i;
    fin>>n;
    fin>>cuv;
    for(i=0;i<n;i++)
        a[i+1]=(cuv[i]-'a')+1;
}
void Interclasare(int st,int m,int dr)
{
    int i,j,k;
    i=st;
    j=m+1;
    k=0;
    while(i<=m and j<=dr)
        if(a[i]<=a[j])
        b[++k]=a[i++];
    else
    {
        b[++k]=a[j++];
       cnt+=m-i+1;
    }
    while(i<=m)
        b[++k]=a[i++];
    while(j<=dr)
        b[++k]=a[j++];
    for(i=1;i<=k;i++)
        a[st++]=b[i];
}
void Mergesort(int st,int dr)
{
    int m;
    if(dr-st<=1)
    {
        if(a[st]>a[dr])
        {
            cnt++;
            swap(a[st],a[dr]);
        }
    }
    else
    {
        m=(st+dr)/2;
       Mergesort(st,m);
        Mergesort(m+1,dr);
        Interclasare(st,m,dr);
    }
}
int main()
{
    Citire();
    Mergesort(1,n);
    fout<<cnt<<"\n";
    fin.close();
    fout.close();
    return 0;
}