Cod sursa(job #279454)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 12 martie 2009 20:30:36
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <fstream>
#include <string>
using namespace std;
int N,cnt[32];
string a,b;
int merge(int l,int r){
    if (l==r) return 0;
    int i,j,k,nr,m=(l+r)/2,p=m;
    nr=merge(l,m)+merge(m+1,r);
    for (i=l,j=m+1,k=l;i<=m || j<=r;)
      if ( j>r || (i<=m && a[i]<=a[j]) )
        nr+=p-m,
        b[k++]=a[i++];
      else
       {
        if (a[j]<a[i]) p=j;               
        b[k++]=a[j++];
       }
    for (i=l;i<=r;++i) a[i]=b[i];
    return nr;
    }
int main(){
    ifstream f("litere.in");
    ofstream g("litere.out");
    f>>N;
    getline(f,a);
    getline(f,a);
    b.resize(N);
    g<<merge(0,N-1);
    return 0;
    }