Cod sursa(job #2674557)

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

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

int v[10000001];
int n;
struct nod
{
    int info;
    nod * urm;
    nod * prev;
}*p[10000001], *u[10000001];
int countDigits(int x)
{
    int nr=0;
    while(x!=0) nr++, x/=n;
    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 adaug(int i, int x)
{
    nod * aux = new nod;
    aux->info=x;
    aux->prev=NULL;
    aux->urm=p[i];
    if(p[i]!=NULL)p[i]->prev=aux;
    p[i]=aux;
    if(u[i]==NULL)
    {
        u[i]=aux;
    }
}
void radixSort(int v[])
{
    int steps=countDigits(getMaxValue(v));
    int power=1;
    int i, k;
    for(k=1; k<=steps; k++)
    {
        for(i=0; i<n; i++)
        {
            u[i]=NULL;
            p[i]=NULL;
        }
        for(i=1; i<=n; i++)
        {
            adaug(v[i]/power%n, v[i]);
        }
        int b=n;
        n=0;
        for(i=0; i<b; i++)
        {
            while(u[i]!=NULL)
            {
                v[++n]=u[i]->info;
                nod * sterg=u[i];
                u[i]=u[i]->prev;
                delete sterg;
            }
        }
        power*=n;
    }
}
int main()
{
    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);
    radixSort(v);
    for(int i=1; i<=n; i+=10) fout<<v[i]<<' ';
}