Cod sursa(job #1779954)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 15 octombrie 2016 18:50:44
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <fstream>
#define NMAX 10000001

using namespace std;

ifstream in("radixsort.in");
ofstream out("radixsort.out");
int a[NMAX];
int n,A,B,C;
int H[10][NMAX+1];

int main()
{
    int maxx, nr = 0, p = 1, key, k = 0;
    in >> n >> A >> B >> C;
    in.close();
    a[1] = B;
    maxx = a[1];
    for(int i = 2; i <= n; i++)
    {
        a[i] = (A * a[i-1] + B) % C;
        if (maxx < a[i])
            maxx = a[i];
    }
    while(maxx)
    {
        nr++;
        maxx /= 10;
    }
    ///
    for(int c = 1; c <= nr; c++)
    {
        for(int i = 1; i <= n; i++)
        {
            key = (a[i] / p) % 10;
            H[key][++H[key][0]] = a[i];
        }
        k = 0;
        for(int i = 0; i <= 9; i++)
        {
            for(int j = 1; j <= H[i][0]; j++)
                a[++k] = H[i][j];
            H[i][0] = 0;
        }
        p *= 10;
    }
    for(int i = 1; i <= n; i += 10)
        out << a[i] << " ";
    out.close();
    return 0;
}