Cod sursa(job #1976738)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 4 mai 2017 09:15:17
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<bits/stdc++.h>
#define maxN 10000005
using namespace std;
int n,a,b,c,s,ss,v[maxN],w[maxN],bucket[260];
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=1;i<=n;i++)
        v[i]=(1LL*a*v[i-1]+b)%c;
    for(int j=0;j<32;j+=8)
    {
        for(int i=0;i<256;i++) bucket[i]=0;
        for(int i=1;i<=n;i++)
            bucket[(v[i]>>j)&255]++;
        s=0;
        for(int i=0;i<256;i++)
        {
            ss=s;
            s+=bucket[i];
            bucket[i]=ss;
        }
        for(int i=1;i<=n;i++)
            w[++bucket[(v[i]>>j)&255]]=v[i];
        for(int i=1;i<=n;i++) v[i]=w[i];
    }
    for(int i=1;i<=n;i+=10) printf("%d ",v[i]);
    return 0;
}