Cod sursa(job #1171551)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 15 aprilie 2014 22:02:19
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#define Nmax 10000005
#define MASK 65535

using namespace std;

int N,v[Nmax],stop;
vector <int> L[MASK];

inline void RadixSort()
{
    int grad,len,i,j;
    for(grad=0;grad<stop;++grad)
    {
        for(i=0;i<MASK;++i)
            L[i].clear();
        for(i=1;i<=N;++i)
            L[((v[i]>>(grad*16))&MASK)].push_back(v[i]);
        N=0;
        for(i=0;i<MASK;++i)
        {
            len=L[i].size();
            for(j=0;j<len;++j)
                v[++N]=L[i][j];
        }
    }
}

int main()
{
    int A,B,C,i;
    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*v[i-1]*A+B)%C;
        if(v[i]>MASK)
            stop=max(stop,2);
        else
            stop=max(stop,1);
    }
    RadixSort();
    for(i=1;i<=N;i+=10)
        printf("%d ", v[i]);
    printf("\n");
    return 0;
}