Cod sursa(job #3124033)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 26 aprilie 2023 18:16:01
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
// #include <iostream>
#include <vector>
#define ll long long

using namespace std;

ifstream cin("radixsort.in");
ofstream cout("radixsort.out");

const int NMAX = 1e7;
int n;
int A, B, C;
int a[NMAX + 1];

void countingsort(int a[], int p)
{
    vector<int> b[10];
    for(int i = 1; i <= n; i++)
        b[(a[i] / p) % 10].push_back(a[i]);
    
    int ind = 0;
    for(int i = 0; i <= 9; i++)
        for(int x : b[i])
            a[++ind] = x;
}

void radixsort(int a[])
{
    int maxi = 0;
    for(int i = 1; i <= n; i++)
        maxi = max(maxi, a[i]);

    ll p = 1;
    while(p <= maxi)
        p *= 10;
    p /= 10;

    for(int i = 1; i <= p; i *= 10)
        countingsort(a, i);
}

signed main()
{
    cin >> n >> A >> B >> C;

    a[1] = B;
    for(int i = 2; i <= n; i++)
        a[i] = (1LL * A * a[i - 1] + B) % C;

    radixsort(a);
    for(int i = 1; i <= n; i += 10)
        cout << a[i] << ' ';

    return 0;    
}