Cod sursa(job #1802408)

Utilizator stelian2000Stelian Chichirim stelian2000 Data 10 noiembrie 2016 11:50:31
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <cstdio>

using namespace std;

const int bucket=8,lim=(1<<bucket)-1;

int v[10000010],v1[10000010],vaz[lim+1],n;

void count_sort(int ind)
{
    for(int i=0;i<=lim;i++)
        vaz[i]=0;
    for(int i=1;i<=n;i++)
        vaz[(v[i]>>(ind*bucket))&lim]++;
    for(int i=1;i<=lim;i++)
        vaz[i]=vaz[i]+vaz[i-1];
    for(int i=n;i>=0;i--)
        v1[vaz[(v[i]>>(ind*bucket))&lim]--]=v[i];
    for(int i=1;i<=n;i++)
        v[i]=v1[i];
}

int main()
{
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    int A,B,C;
    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;
    for(int i=0;i<32/bucket;i++)
        count_sort(i);
    for(int i=1;i<=n;i=i+10)
        printf("%d ",v[i]);
    return 0;
}