Cod sursa(job #1494212)

Utilizator andru47Stefanescu Andru andru47 Data 30 septembrie 2015 20:30:29
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
#define BitMAX 32
#define BitMASK 8
#define NMAX 10000020
using namespace std;
int a[NMAX],ap[1<<BitMASK],subap[NMAX],i,N,A,B,C;
void radicz ( int p )
{
    int mask = (1<<BitMASK) - 1 , i;
    memset(ap,0,sizeof(ap));

    for (i=1 ; i <= N ; ++i)
        ap[(a[i]&(mask<<p))>>p]++;

    for (i = 1 ; i <= mask ; ++i)
        ap[ i ] += ap[ i-1 ] ;

    ap[0]=0;

    for (i = mask ; i >= 1 ; --i)
        ap [i] = ap [i-1] ;

    for (i = 1 ; i <= N ; ++i)
        subap[++ap[(a[i]&(mask<<p))>>p]] = a[i] ;

    for (i=1 ; i <= N ; ++i)
        a[i]=subap[i];
    return ;
}
int main()
{
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    scanf("%d %d %d %d\n",&N,&A,&B,&C);
    a[1]=B;
    for (i = 2 ; i <= N ; ++i)
        a[i] = (1LL*A * a[i-1] + 1LL*B) % C ;
    for (i = 0 ; i < BitMAX ; i+=BitMASK)
        radicz ( i ) ;
    for (i = 1 ; i <= N ; i+=10)
        printf( "%d ", a[i] );
    printf ("\n") ;
    return 0 ;
}