Cod sursa(job #3286562)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 14 martie 2025 13:16:37
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

int n;
long long a,b,c;
const int nmax = 10000000;

int v[nmax + 5];
int aux[nmax + 5];
int f[260];

void radix_sort()
{
    int mask_bts = 8;
    const int mask = (1<<mask_bts)-1;

    for(int i = 0;i<=31;i+=mask_bts)
    {
        for(int j=0;j<=mask;j++) f[j]=0;
        for(int j=1;j<=n;j++)
            f[(v[j]>>i)&mask]++;
        for(int j=1;j<=mask;j++)
            f[j]+=f[j-1];
        for(int j=n;j>=1;j--)
            aux[f[(v[j]>>i)&mask]] = v[j],f[(v[j]>>i)&mask]--;
        for(int j=1;j<=n;j++)
            v[j]=aux[j];
    }
}

int main()
{
    fin>>n>>a>>b>>c;
    for(int i=1;i<=n;i++)
        v[i] = (a*v[i-1] + b)%c;
    radix_sort();

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

}