Cod sursa(job #1168580)

Utilizator bogdanmarin69Bogdan Marin bogdanmarin69 Data 9 aprilie 2014 00:32:57
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <cstdio>
#include <cstring>
using namespace std;
#define MAX 10000001
#define DOI16 65536
int v[MAX], w[MAX], n, a, b, c, aux[DOI16], mask, shift;
void radix();
void countsort(int source[], int dest[]);
void afis()
{
    int i;
    for(i=1; i<=n; i+=10)
        printf("%d ", v[i]);
    printf("\n");
}
int main()
{
    int i;
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);
    scanf("%d%d%d%d", &n, &a, &b, &c);
    v[1] = b;
    for(i=2; i<=n; i++)
        v[i] = (1ll*a*v[i-1]+b)%c;
    radix();
    afis();
    return 0;
}
void countsort(int source[], int dest[]){
    int i;
    for(i=1; i<=n; i++)
        aux[source[i]&mask>>shift]++;
    for(i=1; i<DOI16; i++)
        aux[i] += aux[i-1];
    for(i=n; i>=1; i--)
        dest[aux[source[i]&mask>>shift]--] = source[i];
}
void radix()
{
    mask = 0x00ff; shift = 0;
    countsort(v, w);
    memset(aux, 0, sizeof(aux));
    mask = 0xff00; shift = 16;
    countsort(w, v);
}