Cod sursa(job #3183238)

Utilizator abetAlbert Voiculescu abet Data 11 decembrie 2023 11:56:35
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include<fstream>
using namespace std;
using int64=long long;
ifstream in("radixsort.in");
ofstream out("radixsort.out");
const int MAX=1e7;
const int CIF=10;
int n;
int nr[MAX+1];
int cate[CIF],pos[CIF];
int nrnou[MAX+1];
void radixStep(int power){
        for(int d=0;d<CIF;d++)
            cate[d]=0;
        for(int i=0;i<n;i++)
            cate[nr[i]/power%10]++;
        pos[0]=0;
        for(int d=1;d<CIF;d++)
            pos[d]=pos[d-1]+cate[d-1];
        for(int i=0;i<n;i++){
            nrnou[pos[nr[i]/power%10]]=nr[i];
            pos[nr[i]/power%10]++;
        }
        for(int i=0;i<n;i++)
            nr[i]=nrnou[i];
}
void radixSort(void){
        int maxValue;
        for(int i=0;i<n;i++)
            maxValue=max(maxValue,nr[i]);
        for(int64 power=1;power<=maxValue;power*=10)
            radixStep(power);
}
int main()
{
    int a,b,c;
    in>>n>>a>>b>>c;
    nr[0]=b;
    for(long long i=1;i<=n;i++){
        nr[i]=(1LL*a*nr[i-1]+b)%c;
    }
    radixSort();
    for(int i=0;i<n;i+=10)
        out<<nr[i]<<" ";
    return 0;
}