Cod sursa(job #1476386)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 25 august 2015 03:12:29
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int n,a,b,c;
int v[10000006],p[10000006];
int maxtt=0;
void radix()
{
    for(int put=0;put<=maxtt;put++)
    {
        int rst=0;
        for(int i=1;i<=n;i++)
        {
            if((v[i]&(1<<put))==0) ++rst;
        }
        int rrt=n;
        for(int i=n;i>=1;i--)
        {
            if((v[i]&(1<<put))==0)
            {
                p[rst]=v[i];
                rst--;
            }
            else
            {
                p[rrt]=v[i];
                rrt--;
            }
        }
        for(int i=1;i<=n;i++) v[i]=p[i];
    }
}
int main()
{
    freopen ("radixsort.in","r",stdin);
    freopen ("radixsort.out","w",stdout);
    scanf("%d%d%d%d",&n,&a,&b,&c);
    v[1]=b;
    if(maxtt<log2(b)) maxtt=log2(b);
    for(int i=2;i<=n;i++)
    {
        v[i]=(a*v[i-1]+b)%c;
        int nr=log2(v[i]);
        if(maxtt<nr) maxtt=nr;
    }
    radix();
    for(int i=1;i<=n;i+=10) printf("%d ",v[i]);
    printf("\n");
}