Cod sursa(job #1821972)

Utilizator savulescustefanSavulescu Stefan savulescustefan Data 3 decembrie 2016 22:58:55
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>
#include <vector>
using namespace std;
vector <int> d[260];
int a,b,c,n,p,p1,i,j,nr,v[10000004],k;
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 (i=2;i<=n;i++)
        v[i]=(1LL*a*v[i-1]+b)%c;
    p=1;
    p1=1;
    while (p1<16777216)
    {
        p*=256;
        for (i=1;i<=n;i++)
            d[v[i]%p/p1].push_back(v[i]);
        nr=0;
        for (i=0;i<=255;i++)
        {
            k=d[i].size();
            for (j=0;j<=(k-1);j++)
                v[++nr]=d[i][j];
            d[i].clear();
        }
        p1*=256;
    }
    for (i=1;i<=n;i++)
        d[v[i]/p].push_back(v[i]);
    nr=0;
    for (i=0;i<=255;i++)
    {
        k=d[i].size();
        for (j=0;j<=(k-1);j++)
            v[++nr]=d[i][j];
        d[i].clear();
    }
    for (i=1;i<=n;i+=10)
        printf ("%d ", v[i]);
    return 0;
}