Cod sursa(job #1168586)

Utilizator bogdanmarin69Bogdan Marin bogdanmarin69 Data 9 aprilie 2014 01:09:14
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 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], shift;
unsigned mask;
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 = 0x0000ffff; shift = 0;
    countsort(v, w);
    memset(aux, 0, sizeof(aux));
    mask = 0xffff0000; shift = 16;
    countsort(w, v);
}