Cod sursa(job #2611750)

Utilizator georgecristian2002Raducanu George-Cristian georgecristian2002 Data 7 mai 2020 16:00:28
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
using namespace std;

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

const int dim = 10000005;
int n,v[dim],nr[(1<<9)],poz[(1<<9)],aux[dim];

int main()
{
    long long int a,b,c;
    fin >> n >> a >> b >> c;
    v[0] = b;
    int maxi = b;
    for (int i=1; i<n; i++)
    {
        v[i] = (1ll*a * v[i-1] + b)%c;
        maxi = max(maxi, v[i]);
    }
    int B = (1<<8);
    int nc = 0;
    int cif;
    while (maxi != 0)
    {
        nc++;
        maxi /= B;
    }
    int p=1;
    for (int k=0; k<nc; k++)
    {
        for (int i=0; i<n; i++)
        {
            cif = v[i]/p%B;
            nr[cif]++;
        }
        poz[0] = 0;
        for (int j=1; j<B; j++)
        {
            poz[j] = poz[j-1] + nr[j-1];
        }
        for (int i=0; i<n; i++)
        {
            cif = v[i]/p%B;
            aux[poz[cif]++] = v[i];
        }
        for (int i=0; i<n; i++)
        {
            v[i] = aux[i];
        }
        p*=B;
    }
    for (int i=0; i<n; i += 10)
        fout << v[i] <<' ';
    fin.close();
    fout.close();
    return 0;
}