Cod sursa(job #2674592)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 19 noiembrie 2020 17:58:43
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

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

int v[10000001], v_nou[10000001], d[10000001];
int n, pbaza;
int countDigits(int x)
{
    int nr=0;
    while(x!=0) nr++, x=x>>(pbaza);
    return nr;
}
int getMaxValue(int v[])
{
    int mx=v[1];
    for(int i=2; i<=n; i++)
    {
        if(v[i]>mx) mx=v[i];
    }
    return mx;
}
void radixSort(int v[])
{
    int steps=countDigits(getMaxValue(v));
    int power=0;
    int i, k, bucket;
    for(k=1; k<=steps; k++)
    {
        for(i=1; i<=n; i++)
        {
            bucket=( (v[i]>>power) & ((1<<pbaza)-1) );
            d[bucket]++;
        }

        int aux=(1<<pbaza);
        for(i=1; i<aux; i++) d[i]=d[i]+d[i-1];
        for(i=n; i>=1; i--)
        {
            bucket=( (v[i]>>power) & ((1<<pbaza)-1) );
            v_nou[d[bucket]]=v[i];
            d[bucket]--;
        }
        for(i=1; i<=n; i++)v[i]=v_nou[i];
        for(i=0; i<aux; i++) d[i]=0;

        power=power+pbaza;
    }
}
int main()
{
    /*fin>>n; for(int i=1; i<=n; i++) fin>>v[i];
    radixSort(v);
    for(int i=1; i<=n; i++) cout<<v[i]<<' ';*/
    int a, b, c;
    fin>>n>>a>>b>>c;
    v[1]=b%c;
    for(int i=2; i<=n; i++)
    {
        v[i]=(1LL*a*v[i-1]%c+b)%c;
    }
    //sort(v+1, v+n+1);
    pbaza=8;
    radixSort(v);
    for(int i=1; i<=n; i+=10) fout<<v[i]<<' ';

}