Cod sursa(job #330657)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 11 iulie 2009 02:12:06
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include<fstream>
using namespace std;
int total;
int n;char linie[10001];
int mergeinv(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];
int  k1=1,k2=1,contor=0,numarat=0,pivot=in;
while(k1<=(mij-in+1) && k2<=(sf-mij))
 {if(numarat==0 && l[k1]>r[k2]) {contor+=mij-in+1-k1+1;numarat=1;}
  if(l[k1]>r[k2]) {linie[pivot]=r[k2];k2++; numarat=0;}
   else{linie[pivot]=l[k1];k1++;}
  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++;}
                      
 return contor;    
     }
int merge(int in,int sf)
{int total=0;
if(in<sf)
 {int mij=(in+sf)/2;
  total+=merge(in,mij);
  total+=merge(mij+1,sf);
  total+=mergeinv(in,mij,sf);
          
          }
    
   return total; 
    } 
   
   
int main()
{ifstream in("litere.in");
ofstream out("litere.out");
in>>n;
in.getline(linie,10001);
in.getline(linie,10001);
out<<merge(0,n-1);

return 0;    
    }