Cod sursa(job #2609260)

Utilizator stefanpiturStefan Alexandru Pitur stefanpitur Data 2 mai 2020 12:59:41
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <cstdio>
#include <iostream>	
using namespace std;
	
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
	
const int N = 10000000;
const int B = (1 << 17);
	
int poz[B], nr[B];
int v[N], aux[N];
	
int main()	
{
    int n,a,b,c,i,j,k,vmax,nc,p,cif;
    fin >> n >> a >> b >> c;
    v[0] = vmax = b;
    for(i=1; i<n; i++){
        v[i] = (1LL * a * v[i-1] + 1LL * b) % c;
        vmax = max(vmax, v[i]);
    }
    nc = 0;
    while(vmax){
        nc++;
        vmax /= B;
    }
    p = 0;
    for(k=0; k<nc; k++){
        for(j=0; j<B; j++)
            nr[j] = 0;
        for(i=0; i<n; i++){
            cif = (v[i] >> p) & (B - 1);
            nr[cif]++;
        }
        poz[0] = 0;
        for(j=1; j<B; j++)
            poz[j] = poz[j-1] + nr[j-1];
        for(i=0; i<n; i++){
            cif = (v[i] >> p) & (B - 1);
            aux[poz[cif]++] = v[i];
        }
        for(i=0; i<n; i++)
            v[i] = aux[i];
        p += 17;
    }
    for(i=0; i<n; i+=10)
        fout << v[i] << " ";	
    return 0;
}