Cod sursa(job #1558004)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 28 decembrie 2015 16:25:41
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int nmax=10000000;
int v[nmax+5],n,RAD;
void baga(int a[],int b[],int bi)
{
    int nr[1<<8];
    int po[1<<8];
    int i;

    memset(nr,0,sizeof(nr));

    for(i=0;i<n;i++)
        nr[((a[i]>>(bi*8))&RAD)]++;

    po[0] = 0;
    for(i=1;i<(1<<8);i++)
        po[i]=po[i-1]+nr[i-1];

    for(i=0;i<n;i++)
    {
        b[po[(a[i]>>(bi*8))&RAD]]=a[i];
        po[(a[i]>>(bi*8))&RAD]++;
    }
}

int main()
{
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    int a,b,c;
    scanf("%d%d%d%d",&n,&a,&b,&c);
    v[0]=b;
    int i;
    RAD=0;
    for(i=0;i<8;i++)
        RAD+=(1<<i);
    for(i=1; i<n; i++)
        v[i]=(1LL*v[i-1]*a+b)%c;

    int *temp=new int[n+1];
    for(i=0; i<sizeof(int);i++)
    {
        if(i%2==0)
            baga(v,temp,i);
        else
        baga(temp,v,i);
    }
    if(i%2==1)
    {
        for(i=1;i<n;i++)
            v[i]=temp[i];
    }
    for(i=0; i<n; i+=10)
        printf("%d ",v[i]);
    printf("\n");

    return 0;
}