Cod sursa(job #1874530)

Utilizator ZeBuGgErCasapu Andreas ZeBuGgEr Data 10 februarie 2017 08:41:35
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<cstdio>

using namespace std;

const int bucket=8,lim=(1<<8)-1;
int n,a,b,c;
int vaz[lim+1],v[10000001],temp[10000001];

int get_rest(int nr,int ind)
{
    return lim&(nr>>(ind*bucket));
}

void solve(int indice)
{
    for(int i=0;i<=lim;i++)
    {
        vaz[i]=0;
    }
    for(int i=1;i<=n;i++)
    {
        vaz[get_rest(v[i],indice)]++;
    }
    for(int i=1;i<=lim;i++)
    {
        vaz[i]+=vaz[i-1];
    }
    for(int i=n;i>0;i--)
    {
        temp[vaz[get_rest(v[i],indice)]]=v[i];
        vaz[get_rest(v[i],indice)]--;
    }
    for(int i=1;i<=n;i++)
    {
        v[i]=temp[i];
    }
}

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

    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++)
    {
        solve(i);
    }
    for(int i=1;i<=n;i+=10)
    {
        printf("%d ",v[i]);
    }
}