Cod sursa(job #1668352)

Utilizator sorynsooSorin Soo sorynsoo Data 29 martie 2016 19:05:30
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
#include <string.h>
#include <queue>
using namespace std;

#define MAXN 10000005


int n, a, b, c;
long long v[MAXN];
queue<int> coada[260];
int biti(int pas, int nr)
{
    return ( nr >>(pas*8) ) & 255 ;
}

void doSort(int pas, long long V[])
{
    int i, crt;
    for (i=0; i<n; i++)
        coada[ biti(pas, v[i] ) ].push( v[i] );


    crt = 0;
    for(i=0; i<=255; i++)
    {
        while(!coada[i].empty())
        {
            v[crt++]=coada[i].front();
            coada[i].pop();
        }
    }

}
void RadixSort()
{
    int i;
    for(i=0; i<4; i++)
        doSort(i, v);
}

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

    int i;
    scanf("%d %d %d %d", &n, &a, &b, &c);

    v[0] = b;
    for(i=1; i<n; i++)
        v[i] = ( a * v[i-1] + b ) % c;

    RadixSort();
    for(i=0; i<n; i+=10)
        printf("%d ", v[i]);
    return 0;

}