Cod sursa(job #330471)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 10 iulie 2009 03:48:38
Problema Litere Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<fstream>
using namespace std;
int contor=0;int n;
char linie[10001];
void merge(int in,int mij,int sf)
{char l[5001],r[5001];
for(int i=1;i<=mij-in+1;i++)
 l[i]=linie[i+in-1];
for(int j=1;j<=sf-mij;j++)
  r[j]= linie[j+mij];
for(int i=1;i<=mij-in+1;i++)
 for(int j=1;j<=sf-mij;j++)
  if(l[i]>r[j]) contor++;  
int k1=1,k2=1,pivot=in;
while(k1<=(mij-in+1) && k2<=(sf-mij))
 {if(l[k1]<r[k2]) {linie[pivot]=l[k1];k1++;}
  else {linie[pivot]=r[k2];k2++;}
      pivot++;               
                     }     
 if(k1<=(mij-in+1)) while(k1<=(mij-in+1))  {linie[pivot]=l[k1];k1++;pivot++;}
 else    while(k2<=(sf-mij))  {linie[pivot]=r[k2];k2++;pivot++;}
     }
void mergesort(int in,int sf)
{if(in<sf)
{int mij=(in+sf)/2;
 mergesort(in,mij);
 mergesort(mij+1,sf);
 merge(in,mij,sf);
          
          }
     
     }     
int main()
{ifstream in("litere.in");
ofstream out("litere.out");
char c;
in>>n;in.getline(linie,10001);
in.getline(linie,10001);
 
mergesort(0,n-1);
out<<contor;

return 0;}