Cod sursa(job #1244039)

Utilizator andreey_047Andrei Maxim andreey_047 Data 16 octombrie 2014 18:36:27
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <cstdio>
#define Nmax 10000005
#define MASK 65535
#include <iostream>
#define iN "radixsort.in","r",stdin
#define ouT "radixsort.out","w",stdout
using namespace std;

int n,a[Nmax],b[Nmax],c[Nmax],cnt[MASK+10];
void radix()
{
    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)
        {
            b[i]=((a[i]>>grad)&MASK);
           // cout<<a[i]<<' '<<b[i]<<'\n';
            ++cnt[b[i]];
        }
       // cout<<'\n';
        for(i=1;i<=MASK;++i)
            cnt[i]+=cnt[i-1];
        for(i=n;i;--i)
            c[cnt[b[i]]--]=a[i];
        for(i=1;i<=n;++i)
            a[i]=c[i];
    }
}

int main()
{
    int i,x,y,z;
    freopen(iN);
    freopen(ouT);
    scanf("%d%d%d%d", &n,&x,&y,&z);
    a[1]=y;
    for(i=2;i<=n;++i)
        a[i]=(1LL*a[i-1]*x + 1LL*y) % z;
    radix();
    for(i=1;i<=n;i+=10)
        cout << a[i]<<' ';
    cout <<'\n';
    return 0;
}