Cod sursa(job #2611802)

Utilizator tomitza.1604Sacuiu TomaAndrei tomitza.1604 Data 7 mai 2020 16:42:06
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream in("radixsort.in");
ofstream out("radixsort.out");

const int N = 10000005;
const int NB = 8;
int v[N], aux[N], nr[(1<<8)+10], poz[(1<<8)+10], n;

int main()
{
    long long int a, b, c;
    in >> n >> a >> b >> c;

    v[0] = b;
    int maxx = b;
    for(int i=1; i<n; i++)
    {
        v[i] = (a*v[i-1]+b)%c;
        maxx = max(maxx, v[i]);
    }
    int B = (1<<8), NC=0;
    while (maxx != 0)
    {
        NC++;
        maxx /= B;
    }
    int m = B-1;
    for(int k = 0 ; k<NC; k++)
    {
        int nb = k*NB;
        for(int j=0; j<B; j++)
        {
            nr[j]=0;
        }
        for(int i=0; i<n; i++)
        {
            int cif = (v[i]>>nb)&m;
            nr[cif]++;
        }
        poz[0]=0;
        for(int j=0; j<B; j++)
        {
            poz[j]=poz[j-1]+nr[j-1];
        }
        for(int i=0; i<n; i++)
        {
            int cif = (v[i]>>nb)&m;
            aux[poz[cif]++] = v[i];
        }
        for(int i = 0; i < n; i++) v[i] = aux[i];
    }
    for(int i=0; i<n; i=i+10)
	{
        out<<v[i]<<" ";
	}
    return 0;

}