Cod sursa(job #1171535)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 15 aprilie 2014 21:38:20
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#define Nmax 10000005

using namespace std;

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

inline int Get_Digit(int x, int cif)
{
    while(cif--)
        x/=10;
    return x%10;
}

inline void RadixSort()
{
    int cif,i,j,len;
    for(cif=0;cif<stop;++cif)
    {
        for(i=0;i<10;++i)
            L[i].clear();
        for(i=1;i<=N;++i)
            L[Get_Digit(v[i],cif)].push_back(v[i]);
        N=0;
        for(i=0;i<10;++i)
        {
            len=L[i].size();
            for(j=0;j<len;++j)
                v[++N]=L[i][j];
        }
    }
}

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