Cod sursa(job #2866461)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 9 martie 2022 18:45:32
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <vector>

int main(){
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);
    int n, i, j, arr, start;
    long long vmax, p, a, b, c, x;
    std::vector<int> t[2][10];
    
    std::cin >> n >> a >> b >> c;

    t[0][b % 10].push_back((int)b);
    vmax = b;
    x = b;
    for(i = 1; i < n; i ++){
        x = (a * x + b) % c;
        t[0][x % 10].push_back((int)x);
        vmax = std::max(vmax, x);
    }

    p = 10;
    arr = 1;
    do{
        p *= 10;
        for(i = 0; i < 10; ++ i){
            for(j = 0; j < t[arr ^ 1][i].size(); j ++)
                t[arr][(t[arr ^ 1][i][j] % p) / (p / 10)].push_back(t[arr ^ 1][i][j]);
            t[arr ^ 1][i].clear();
        }
        arr = (arr ^ 1);
    }
    while(vmax / p > 0);
    arr = (arr ^ 1);
    start = 0;
    for(i = 0; i < 10; i ++){
        for(j = start; j < t[arr][i].size(); j += 10)
            std::cout << t[arr][i][j] << " ";
        start = j - t[arr][i].size();
    } 
    return 0;
}