Cod sursa(job #1401491)

Utilizator sergiunascaSergiu Nasca sergiunasca Data 25 martie 2015 22:07:23
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define NMax 10000006
using namespace std;
int n,a,b,c,x[NMax],out[NMax],countV[1<<8];

void radix_sort(int shift,int bit)
{
    int mash = (1<<bit)-1;
    for(int i=1;i<=(1<<bit);++i)countV[i] = 0;
    for(int i=1;i<=n;++i)
    {
        countV[ (x[i]>>shift)&mash ]++;
    }
    for(int i=1;i<=mash;++i)
    {
        countV[i] += countV[i-1];
    }
    for(int i=mash;i>=1;--i)countV[i] = countV[i-1];
    countV[0] = 0;
    for(int i=1;i<=n;++i)
    {
        out[ ++countV[ (x[i]>>shift)&mash ] ] = x[i];
    }
    for(int i=1;i<=n;++i)x[i] = out[i];
}

int main()
{
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    scanf("%d %d %d %d",&n,&a,&b,&c);
    x[1] = b;
    for(int i=2;i<=n;++i)
    {
        x[i] = (a * x[i-1] + b) % c;
    }
    radix_sort(0,8);
    radix_sort(8,8);
    radix_sort(16,8);
    radix_sort(24,8);
    //radix_sort(16,16);
    for(int i=1;i<=n;i+=10)printf("%d ",x[i]);
    return 0;
}