Cod sursa(job #1969671)

Utilizator george_stelianChichirim George george_stelian Data 18 aprilie 2017 16:22:27
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <cstdio>

using namespace std;

const int bits=8;
int v[10000010],v1[10000010],vaz[1<<bits],n;

int get_num(int a,int nr)
{
    return (a>>(bits*nr))&((1<<bits)-1);
}

void count_sort(int nr)
{
    for(int i=0;i<(1<<bits);i++) vaz[i]=0;
    for(int i=1;i<=n;i++) vaz[get_num(v[i],nr)]++;
    for(int i=1;i<(1<<bits);i++) vaz[i]+=vaz[i-1];
    for(int i=n;i;i--)
        v1[vaz[get_num(v[i],nr)]--]=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*v[i-1]*a+b)%c;
    for(int i=0;i<32/bits;i++)
        count_sort(i);
    for(int i=1;i<=n;i+=10) printf("%d ",v[i]);
    return 0;
}