Cod sursa(job #1399751)

Utilizator sergiunascaSergiu Nasca sergiunasca Data 24 martie 2015 21:42:15
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int n,a,b,c,mod,per;
std::vector<int> x,cifre[10];

void radix_sort()
{
    bool continuare = false;
    for(int i=1;i<=n;++i)
    {
        int aux = (x[i]%mod)/per ;
        if(aux>0)continuare = true;
        cifre[ aux ].push_back(x[i]);
    }
    n=0;
    for(int i=0;i<=9;++i)
    {
        for(int j=0;j<cifre[i].size();++j)x[++n] = cifre[i][j];
        cifre[i].clear();
    }
    mod *= 10;
    per *= 10;
    if(continuare)radix_sort();
}

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