Cod sursa(job #1628723)

Utilizator ZeBuGgErCasapu Andreas ZeBuGgEr Data 4 martie 2016 10:17:30
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<cstdio>

using namespace std;

int val[10000010],n,a,b,c,hold[16],newval[10000010];
int bkt=0;

void solve()
{
    for(int i=0;i<16;i++)
    {
        hold[i]=0;
    }
    for(int i=1;i<=n;i++)
    {
        hold[(val[i]>>bkt)&15]++;
    }
    for(int i=1;i<16;i++)
    {
        hold[i]+=hold[i-1];
    }
    for(int i=n;i>=1;i--)
    {
        int temp;
        temp=(val[i]>>bkt)&15;
        newval[hold[temp]]=val[i];
        hold[temp]--;
    }
    for(int i=1;i<=n;i++)
    {
        val[i]=newval[i];
    }
}

void radix()
{
    for(bkt;bkt<32;bkt+=4)
    {
        solve();
    }
}

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

    scanf("%d %d %d %d",&n,&a,&b,&c);

    val[1]=b;

    for(int i=2;i<=n;i++)
    {
        val[i]=(1LL*val[i-1]*a+b)%c;
    }

    radix();

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