Cod sursa(job #1504614)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 17 octombrie 2015 22:59:34
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <cstdio>
#define baza 2
using namespace std;
int n,a,b,c,maxim,ptx;
int v[10000006],out[10000006];
int ct[5];
void counting(int nr)
{
    for(int i=0;i<4;i++) ct[i]=0;
    for(int i=1;i<=n;i++) ct[(v[i]>>ptx)&3]++;
    for(int i=1;i<4;i++) ct[i]+=ct[i-1];
    for(int i=n;i>=1;i--)
    {
        int nr=(v[i]>>ptx)&3;
        out[ct[nr]]=v[i];
        ct[nr]--;
    }
   /// printf("\n");
    for(int i=1;i<=n;i++) v[i]=out[i];
}
void radix()
{
    ptx=0;
    for(int nr=1;(maxim>>ptx)>0;nr<<=2)
    {
        counting(nr);
        ptx+=2;
    }
}
int main()
{
    freopen ("radixsort.in","r",stdin);
    freopen ("radixsort.out","w",stdout);
    scanf("%d%d%d%d",&n,&a,&b,&c);
   // for(int i=1;i<=n;i++) scanf("%d",&v[i]);
    v[1]=b;
    for(int i=2;i<=n;i++)
    {
        v[i]=(1LL*a*v[i-1]+b)%c;
        if(maxim<v[i]) maxim=v[i];
    }
    radix();
    for(int i=1;i<=n;i+=10) printf("%d ",v[i]);
}