Cod sursa(job #1400846)

Utilizator sergiunascaSergiu Nasca sergiunasca Data 25 martie 2015 14:50:13
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int n,a,b,c,maxi;
std::vector<int> x,cifre[10];

void radix_sort(int maxi)
{
    for(int i=1;i<=maxi;i*=10)
    {
        for(int j=1;j<=n;++j)
        {
            cifre[ (x[j]/i)%10 ].push_back(x[j]);
        }
        n = 0;
        for(int j=0;j<=9;++j)
        {
            for(int k=0;k<cifre[j].size();++k)x[++n] = cifre[j][k];
            cifre[j].clear();
        }
    }
}

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