Cod sursa(job #1376343)

Utilizator atatomirTatomir Alex atatomir Data 5 martie 2015 17:07:59
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <cstdio>

using namespace std;

#define maxN 10000011
#define maxBit 31

long long n,a,b,c,i,act,bit;
long s=0,d=1,cnt,c1,c2;
long v[2][maxN];

int main()
{
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);

    scanf("%lld %lld %lld %lld",&n,&a,&b,&c);act=b;
    for(i=1;i<=n;i++){
        v[s][i] = act;
        act = (act*a+b)%c;
    }

    for(bit=0;bit<=maxBit;bit++){
        long mask = 1<<bit;

        cnt=0;
        for(i=1;i<=n;i++)
            if((v[s][i]&mask)==0) cnt++;

        c1=0; c2=cnt;
        for(i=1;i<=n;i++){
            if(v[s][i]&mask) v[d][++c2] = v[s][i];
            else             v[d][++c1] = v[s][i];
        }

        s ^= 1; d^=1 ;
    }

    for(i=1;i<=n;i+=10) printf("%ld ",v[s][i]);

    return 0;
}