Cod sursa(job #1143742)

Utilizator cbanu96Banu Cristian cbanu96 Data 15 martie 2014 22:05:45
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <cstdio>
#include <cstring>

#define FILEIN "radixsort.in"
#define FILEOUT "radixsort.out"
#define NMAX 10000004
#define AMAX 2147483647

int N;
int A[NMAX], B[NMAX];

void radix() {
    const int base = 256;
    int buckets[base];

    int exp = 0;

    while ( exp < 4 ) {
        memset(buckets, 0, sizeof(buckets));
        for ( int i = 1; i <= N; i++ ) {
            buckets[(A[i] >> (exp*8)) & 0xFF]++;
        }
        for ( int i = 1; i < base; i++)
            buckets[i] += buckets[i-1];
        for ( int i = N; i >= 1; i-- ) {
            B[buckets[(A[i] >> (exp*8)) & 0xFF]--] = A[i];
        }

        memcpy(A, B, sizeof(A[0]) * (N + 1));

        exp++;
    }
}



int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    int x, y, z;
    scanf("%d %d %d %d", &N, &x, &y, &z);

    A[1] = y;
    for ( int i = 2; i <= N; i++ ) {
        A[i] = (x * A[i-1] + y) % z;
    }

    radix();

    for ( int i = 1; i <= N; i += 10 ) {
        printf("%d ", A[i]);
    }
    printf("\n");

    return 0;
}