Cod sursa(job #1097122)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 3 februarie 2014 00:20:12
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<fstream>
#include<cstring>
using namespace std;
const int dim=65535;
int i,a[2][10000005],n,indx[65540],indc=1,indp=0,buckt[65540];
long long aa,b,c;

int getbyte(int x, int nr) {
    if (nr==1) return(x&65535);
      else {
           x>>=16;
           return(x&65535);
           }
}

void countsort(int nr){
     memset(buckt,0,sizeof(buckt));
     for (i=1; i<=n; ++i) ++buckt[getbyte(a[indp][i],nr)];
     
     indx[0]=0;
     for (i=1; i<=dim; ++i) indx[i]=indx[i-1]+buckt[i-1];
     
     for (i=1; i<=n; ++i) a[indc][ ++indx[getbyte(a[indp][i],nr)] ]=a[indp][i];
}    

int main(void) {
    ifstream fin("radixsort.in");
    ofstream fout("radixsort.out");
    fin>>n>>aa>>b>>c;
    a[indp][1]=b;
    for (i=2; i<=n; ++i) a[indp][i]=(aa*(long long)a[indp][i-1]+b)%c;
    
    countsort(1);
     swap(indc,indp);
    countsort(2);    

    for (i=1; i<=n; i+=10) fout<<a[indc][i]<<" ";
    
  return(0);
}