Cod sursa(job #1092129)

Utilizator andrettiAndretti Naiden andretti Data 26 ianuarie 2014 16:48:46
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<stdio.h>
#include<algorithm>
#include<cstring>
#define maxn 10000005
using namespace std;

int N,A,B,C;
int maxDig;
int v[maxn],bucket[maxn];

void read(){
    scanf("%d%d%d%d",&N,&A,&B,&C);
}

int nrOfDig(int x)
{
    int nr=0; for(;x;x/=10,nr++);
    return nr;
}
void gen()
{
    v[1]=B; maxDig=max(maxDig,nrOfDig(v[1]));
    for(int i=2;i<=N;i++)
     v[i]=((1LL*A*v[i-1])%C+1LL*B)%C,
     maxDig=max(maxDig,nrOfDig(v[i]));
}

void radix_sort(int L,int R)
{
    int step,Dig,nr;
    int ind[10];
    for(Dig=1,step=1;step<=maxDig;Dig*=10,step++)
    {
        memset(ind,0,sizeof(ind)); nr=0;
        for(int i=L;i<=R;i++) ind[v[i]/Dig%10]++;
        for(int i=1;i<=9;i++) ind[i]+=ind[i-1];
        for(int i=R;i>=L;i--) bucket[ind[v[i]/Dig%10]--]=v[i];
        for(int i=L;i<=R;i++) v[i]=bucket[++nr];
    }
}

void print()
{
    for(int i=1;i<=N;i+=10)
      printf("%d ",v[i]);
}

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

    read();
    gen();
    radix_sort(1,N);
    print();

    fclose(stdin);
    fclose(stdout);
    return 0;
}