Cod sursa(job #1494003)

Utilizator andru47Stefanescu Andru andru47 Data 30 septembrie 2015 13:24:13
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 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] ;

    memcpy(a,subap,sizeof(subap));
    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] = (A * a[i-1] + 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 ;
}