Cod sursa(job #1171559)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 15 aprilie 2014 22:10:55
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <cstdio>
#define Nmax 10000005
#define MASK 65535

using namespace std;

int N,a[Nmax],a1[Nmax],a2[Nmax],cnt[MASK+5];

inline void RadixSort()
{
    int grad,i;
    for(grad=0;grad<=16;grad+=16)
    {
        for(i=0;i<=MASK;++i)
            cnt[i]=0;
        for(i=1;i<=N;++i)
        {
            a1[i]=((a[i]>>grad)&MASK);
            ++cnt[a1[i]];
        }
        for(i=1;i<=MASK;++i)
            cnt[i]+=cnt[i-1];
        for(i=N;i;--i)
            a2[cnt[a1[i]]--]=a[i];
        for(i=1;i<=N;++i)
            a[i]=a2[i];
    }
}

int main()
{
    int i,A,B,C;
    freopen ("radixsort.in","r",stdin);
    freopen ("radixsort.out","w",stdout);
    scanf("%d%d%d%d", &N,&A,&B,&C);
    a[1]=B;
    for(i=2;i<=N;++i)
        a[i]=(1LL*a[i-1]*A + 1LL*B) % C;
    RadixSort();

    for(i=1;i<=N;i+=10)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}