Cod sursa(job #1313433)

Utilizator priestnoobFMI - Dan Nema priestnoob Data 10 ianuarie 2015 17:38:41
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<stdio.h>
#include<algorithm>

using namespace std;

#define nmax 10000005
#define base 255

int n,a,b,c,v[nmax],bucket[base],u[nmax];

void citire()
{
    scanf("%d%d%d%d",&n,&a,&b,&c);
    v[1]=b;
    for(int i=2;i<=n;++i)
        v[i]= (1LL* a * v[i-1] + b ) % c;
}

void afisare()
{
    for(int i=1;i<=n;i+=10)
        printf("%d ",v[i]);
}

void radixsort()
{
    long long exp=1,i;
    while( 2147483647 > exp )
    {
        for(i=0;i<=base;++i) bucket[i]=0;
        for(i=1;i<=n;++i) bucket[ ( v[i] / exp ) % (base+1) ]++;
        for(i=1;i<=base;++i) bucket[i]+=bucket[i-1];
        for(i=n;i>=1;--i) u[ bucket[ ( v[i] / exp ) % (base+1) ]-- ] = v[i];
        for(i=1;i<=n;++i) v[i]=u[i];
        exp*=base+1;
    }
}

int main()
{
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    citire();
    radixsort();
    afisare();
}