Cod sursa(job #2674387)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 19 noiembrie 2020 00:15:10
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");

int n;
struct nod
{
    int info;
    nod * urm;
}*p[10000001];
void adaug(int i, int x)
{
    nod *aux=new nod;
    aux->info=x;
    aux->urm=p[i];
    p[i]=aux;
}
int getMaxValue(int v[])
{
    int i, mx=0; for(i=1; i<=n; i++) mx=max(mx, v[i]);
    return mx;
}
void radixsort(int v[])
{
    int i, j, k, mx, steps=0, power=1, nr_aux;
    mx=getMaxValue(v);
    while(mx!=0)
    {
        steps++;
        mx=mx/n;
    }
    for(k=1; k<=steps; k++)
    {
        for(i=1; i<=n; i++)
        {
            adaug(v[i]/power%n, v[i]);
        }
        int b=n;
        n=0; //simulez golirea vectorului
        for(i=0; i<b; i++)
        {
            nr_aux=0;
            nod * paux=NULL;
            while(p[i]!=NULL)
            {
                nod * aux = new nod;
                aux->info=p[i]->info;
                aux->urm=paux;
                paux=aux;

                nod*sterg=p[i];
                p[i]=p[i]->urm;
                delete sterg;
            }
            while(paux!=NULL)
            {
                v[++n]=paux->info;
                nod*sterg=paux;
                paux=paux->urm;
                delete sterg;
            }
        }
        power*=n;
    }
}
int v[10000001];
int main()
{
    int a, b, c, i;
    fin>>n>>a>>b>>c;
    v[1]=b;
    for(i=2; i<=n; i++)
    {
        v[i]=(a*v[i-1]+b)%c;
    }
    radixsort(v);
    for(int i=1; i<=n; i+=10) fout<<v[i]<<' ';
}