Cod sursa(job #3375134)

Utilizator LucaMirsolea14Luca Mirsolea LucaMirsolea14 Data 10 noiembrie 2026 15:15:42
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

const int N = 1e7 + 10;

unsigned int n, A, B, C;

unsigned int v[N], vaux[N];

void countSort(int zece){

    int vnr[100], i;

    for(i=0;i<=10;i++)
        vnr[i] = 0;

    for(i=1;i<=n;i++){
        vnr[(v[i]/zece)%10]++; /// cifra corespunzatoare
    }

//    fout << "vnr[] : ";
//    for(i=1;i<=10;i++)
//        fout << vnr[i] << " ";
//    fout << endl;

    for(i=0;i<10;i++)
        vnr[i] += vnr[i-1]; /// sume partiale pt a putea vedea usor cate sunt mai mici (in functie de cifra) decat un numar aleatoriu

    for(i=1;i<=n;i++)
        vaux[i] = 0;

//    fout << "vnr[] : ";
//    for(i=0;i<=10;i++)
//        fout << vnr[i] << " ";
//    fout << endl;

    for(i=n;i>0;i--){
        /// vedem pe ce pozitie s-ar afla v[i] (initial) in functie de cate numere
        /// exita cu cifra zece mai mica decat el
        vaux[vnr[(v[i]/zece)%10]] = v[i];
        vnr[(v[i]/zece)%10]--;
    }
    for(i=1;i<=n;i++)
        v[i] = vaux[i];

}

void radixSort(){

    unsigned int i, zece, maxi = 0;

    for(i=1;i<=n;i++)
        maxi = max(maxi, v[i]);

    for(zece=1; zece < 1e9 && zece <= maxi; zece *= 10){
        countSort(zece);
    }

}

int32_t main(){

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

//    for(i=1;i<=n;i++)
//        fout << v[i] << " ";
//    fout << endl;

    radixSort();

    for(i=1;i<=n;i+=10)
        fout << v[i] << " ";

}