Cod sursa(job #1371559)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 3 martie 2015 22:15:47
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>
using namespace std;
ifstream f("litere.in");
ofstream g("litere.out");
long long N,Result,Aux[10005];
char S[10005];
void Read()
{
    f>>N;
    int i;
    for(i=1;i<=N;i++)
        f>>S[i];
}
void DEI(int Left,int Right)
{
    if(Right==Left)
       return;
    int Mid=(Left+Right)/2;
    DEI(Left,Mid);
    DEI(Mid+1,Right);
    int i=Left,j=Mid+1,k=0,Number=0;
    while(i<=Mid && j<=Right)
    {
        if(S[i]>S[j])
            Number++,Aux[++k]=S[j++];
        else
            Aux[++k]=S[i++],Result+=Number;
    }
    if(i<=Mid)
        for(;i<=Mid;i++)
            Aux[++k]=S[i],Result+=Number;
    if(j<=Right)
        for(;j<=Right;j++)
            Aux[++k]=S[j];
    for(i=1;i<=k;i++)
        S[i+Left-1]=Aux[i];
}
int main()
{
    Read();
    DEI(1,N);
    g<<Result<<"\n";
    int i;
    /*for(i=1;i<=99999;i++)
        g<<i<<" ";
    g<<1<<"\n";*/
    return 0;
}