Cod sursa(job #2613609)

Utilizator ionutomutiuIonut Tomutiu ionutomutiu Data 10 mai 2020 00:06:07
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");
int A[1000005];
int B[1000005];
int N, X, Y, Z;
void count_sort (int pos)
{

    int frv[11];
    fill (frv, frv + 10, 0);
    for (int i = 1; i <= N; i++)
        frv[(A[i] / pos) % 10]++;
    for (int i = 1; i < 10; i++)
        frv[i] += frv[i - 1];
    for (int i = N; i > 0; i--)
        B[frv[(A[i] / pos) % 10]--] = A[i];
    for (int i = 1; i <= N; i++)
        A[i] = B[i];
}
int main ()
{
    fin >> N >> X >> Y >> Z;
    A[1] = Y;
    for (int i = 2; i <= N; i++)
        A[i] = (1LL * (X * A[i - 1]) % Z + Y) % Z;
    int maxi = A[1];
    for (int i = 1; i <= N; i++)
        maxi = max (maxi, A[i]);
    for (int i = 1; i <= maxi; i *= 10)
        count_sort (i);
    for (int i = 1; i <= N; i += 10)
        fout << A[i] << " ";
}