Cod sursa(job #2316083)

Utilizator AlexandruGabrielAliciuc Alexandru AlexandruGabriel Data 11 ianuarie 2019 00:47:54
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>
#define N 10000001

using namespace std;

ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");

int a[N], n, A, B, C;
queue <int> Q[10];

void Citire()
{
    fin >> n >> A >> B >> C;
    a[1] = B;
    for (int i = 2; i <= n; i++)
        a[i] = (A * a[i - 1] + B) % C;
}

void CountSort(int ex)
{
    int k = 0;
    for (int i = 1; i <= n; i++)
        Q[a[i] / ex % 10].push(a[i]);
    for (int i = 0; i <= 9; i++)
        while (!Q[i].empty())
        {
            a[++k] = Q[i].front();
            Q[i].pop();
        }
}

void RadixSort()
{
    int maxi = -1;
    for (int i = 1; i <= n; i++)
        maxi = max(maxi, a[i]);
    for (int i = 1; maxi / i != 0; i *= 10)
        CountSort(i);
}

void Afisare()
{
    for (int i = 1; i <= n; i++)
        fout << a[i] << " ";
}

int main()
{
    Citire();
    RadixSort();
    Afisare();
    return 0;
}