Cod sursa(job #3221600)

Utilizator Theo20067Cismaru Theodor-Alexe Theo20067 Data 7 aprilie 2024 15:44:32
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("radixsort.in");
ofstream fout("radixsort.out");
const long long BAZA=100;
int n,V[10000002],aux[10000002],f[BAZA],A,B,C,maxim;
void count_sort(long long digit)
{
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
        f[(V[i]/digit)%BAZA]++;
    for(int i=1;i<BAZA;i++)
        f[i]+=f[i-1];
    for(int i=1;i<=n;i++)
        aux[f[(V[i]/digit)%BAZA]--]=V[i];
    for(int i=1;i<=n;i++)
        V[i]=aux[i];
}
void radix_sort()
{
    for(long long d=1;maxim/d>0;d*=BAZA)
        count_sort(d);
}
int main()
{
	fin>>n>>A>>B>>C;
	maxim=B;
    V[1]=B;
    for(int i=2;i<=n;i++)
    {
        V[i]=(A*1LL*V[i-1]+B)%C;
        maxim=max(maxim,V[i]);
    }
    radix_sort();
    for(int i=1;i<=n;i+=10)
        fout<<V[i]<<" ";
	return 0;
}