Cod sursa(job #1513024)

Utilizator stanciuandreiStanciulescu Andrei stanciuandrei Data 28 octombrie 2015 21:46:14
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("radixsort.in");
ofstream out("radixsort.out");
int v[10000000],n,a,b,c, ma, pw=1;
struct bucket
{
    int val;
    bucket * next;
};
bucket * bk[10];
bucket *start[10];
bucket *celem[10];
void afisare(bucket *p)
{
    while(1)
    {
        cout<<p->val<<" ";
        if(p->next==NULL)
            break;
        p=p->next;
    }
}
void extract()
{
    int cnt=0;
    for(int i=0; i<10; ++i)
    {
        celem[i]=start[i];
        if(celem[i]->next!=NULL)
        {
            celem[i]=start[i]->next;
            while(celem[i]->next!=NULL)
            {
                v[cnt]=celem[i]->val;
                celem[i]=celem[i]->next;
                cnt++;
            }
            v[cnt]=celem[i]->val;
            celem[i]=celem[i]->next;
            cnt++;
        }
    }
}
void add(int pos, int val)
{
    celem[pos]->next=new bucket;
    celem[pos]=celem[pos]->next;
    celem[pos]->next=NULL;
    celem[pos]->val=val;
}
void empt()
{
    for(int i=0; i<10; ++i)
        start[i]->next=NULL, start[i]->val=-1, celem[i]=start[i];
}
void init()
{
    for(int i=0; i<10; ++i)
        bk[i]=new bucket, start[i]=bk[i], celem[i]=start[i];
}
void radix()
{
    do
    {
        empt();
        for(int i=0; i<n; ++i)
        {
            add(v[i]%(pw*10)/pw, v[i]);
        }
        extract();
        pw*=10;
    }
    while(pw<ma);
}
int main()
{
    init();
    empt();
    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;
}