Cod sursa(job #1513261)

Utilizator stanciuandreiStanciulescu Andrei stanciuandrei Data 29 octombrie 2015 10:43:33
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("radixsort.in");
ofstream out("radixsort.out");
int *bucket[10];
int v[10000000],n,a,b,c, ma, pw=1, dim[10];
void empt()
{
    for(int i=0;i<10;++i)
        delete[] bucket[i], dim[i]=0;
}
void copy(int * a, int * b,int dm)
{
    for(int i=0;i<dm;++i)
    {
        b[i]=a[i];
    }
}
void extract()
{
    int cnt=0;
    for(int i=0;i<10;++i)
    {
        if(dim[i]!=0&&bucket[i]!=NULL)
        {
            for(int j=0;j<dim[i];j++)
            {
                v[cnt]=bucket[i][j];
                //cout<<"Extracted "<<v[cnt]<<" from "<<i<<"\n";
                cnt++;
            }
        }
    }
}
void add(int digit, int val)
{
    int *tmp;
    tmp = new int[dim[digit]];
    copy(bucket[digit], tmp, dim[digit]);
    delete[] bucket[digit];
    dim[digit]++;
    bucket[digit]=new int[dim[digit]];
    copy(tmp, bucket[digit], dim[digit]);
    bucket[digit][dim[digit]-1]=val;
    delete[] tmp;
}
void radix()
{
    do
    {
        empt();
        for(int i=0; i<n; ++i)
        {
            add(v[i]%(pw*10)/pw, v[i]);
            //cout<<"Added "<<v[i]<<" to "<<v[i]%(pw*10)/pw<<"\n";
        }
        pw*=10;
        extract();
    }
    while(pw<ma);
}
int main()
{
    in>>n>>a>>b>>c;
    v[0]=b;
    for(int i=0; i<n; ++i)
    {
        v[i]=(a * v[i-1] + b) % c;
        if(ma<v[i])
            ma=v[i];
    }
    radix();
    for(int i=0; i<n; i+=10)
        out<<v[i]<<" ";
    out<<"\n";
    return 0;
}