Cod sursa(job #1400871)

Utilizator sergiunascaSergiu Nasca sergiunasca Data 25 martie 2015 15:14:33
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define NMax 10000000
using namespace std;
int n,a,b,c,maxi,countV[20],x[NMax],out[NMax];

void radix_sort(int maxi)
{
    for(int per=1;per<=maxi;per*=10)
    {
        for(int i=0;i<=n;++i)
        {
            ++countV[ (x[i]/per)%10 ];
        }
        for(int i=1;i<10;++i)
        {
            countV[i] += countV[i-1];
        }
        for(int i=n;i>=0;--i)
        {
            out[ countV[ (x[i]/per)%10 ] - 1 ] = x[i];
            --countV[ (x[i]/per)%10 ];
        }
        for(int i=0;i<=n;++i)
        {
            if(i<=10)countV[i] = 0;
            x[i] = out[i];
        }
    }
}

int main()
{
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    scanf("%d %d %d %d",&n,&a,&b,&c);
    --n;
    x[0] = b;
    for(int i=1;i<=n;++i)
    {
        x[i] = (a * x[i-1] + b) % c;
        if(x[i]>maxi)maxi = x[i];
    }
    radix_sort(maxi);
    for(int i=0;i<=n;i+=10)printf("%d ",x[i]);
    return 0;
}