Cod sursa(job #3255600)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 11 noiembrie 2024 15:57:35
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

const int nmax = 10000000;


const int bits = 31;
const int bit_group_size = 8;
const int base = (1<<bit_group_size)-1;

int n;

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

void radix(int* v)
{

    for(int b = 0 ; b<=bits;b+=bit_group_size)
    {
        for(int i=0;i<=base;i++) f[i] = 0;
        for(int i = 1;i<=n;i++)
            f[(v[i]>>b)&base]++;
        for(int i=1;i<=base;i++) f[i]+=f[i-1];
        for(int i=n;i>=1;i--)
            aux[f[(v[i]>>b)&base]--]=v[i];
        for(int i=1;i<=n;i++) v[i]=aux[i];
    }
}

long long a,b,c;

int main()
{
    fin>>n>>a>>b>>c;
    v[1]=b;
    for(int i=2;i<=n;i++)
        v[i]=(a*v[i-1]+b)%c;
    radix(v);
    for(int i=1;i<=n;i+=10) fout<<v[i]<<' ';
}