Cod sursa(job #1876316)

Utilizator ArambasaVlad Arambasa Arambasa Data 12 februarie 2017 11:22:18
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#define PT(a,m,n) for(int a=m;a<=n;a++)
#define SW(v,b,e,I) for(int i=b;i<=e;i+=I){out<<v[i]<<' ';}
using namespace std;
ifstream in ("radixsort.in");
ofstream out ("radixsort.out");
const int bucket=8,lim=(1<<8)-1;
const int NMax= 10000005;
int n,a,b,c;
int vaz[lim+1],v[NMax],temp[NMax];

int get_rest(int nr,int ind)
{
    return lim&(nr>>(ind*bucket));
}
void SolveStepArg(int arg)
{
    PT(i,0,lim)
    {
        vaz[i]=0;
    }
    PT(i,1,n)
    {
        vaz[get_rest(v[i],arg)]++;
    }
    PT(i,1,lim)
    {
        vaz[i]+=vaz[i-1];
    }
    for(int i=n;i>0;i--)
    {
        temp[vaz[get_rest(v[i],arg)]]=v[i];
        vaz[get_rest(v[i],arg)]--;
    }
    PT(i,1,n)
    {
        v[i]=temp[i];
    }
}
void Read()
{
    in>>n>>a>>b>>c;
}
void Solve()
{
    v[1]=b;
    PT(i,2,n)
    v[i]=(1LL*a*v[i-1]+b)%c;

    PT(i,0,(32/bucket)-1)
    SolveStepArg(i);
}
void Print()
{
    //SW(v,1,n,10)
    for(int i=1;i<=n;i+=10)
    {
        out<<v[i]<<' ';
    }
}
int main()
{
    Read();
    Solve();
    Print();
}