Cod sursa(job #1750918)

Utilizator AplayLazar Laurentiu Aplay Data 31 august 2016 14:23:39
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>

#define NMAX 10000000
#define BYTES 4
#define DIGITS 256
#define byte(x, it) (x >> (it * 8)) & 0xFF

using namespace std;

int N, A, B, C, numbers[NMAX], tNumbers[NMAX];

void countSort(int* A, int* B, int byteNumber) {
    int counter[DIGITS], index[DIGITS];

    memset(counter, 0, sizeof(counter));

    for (int it = 0; it < N; ++it) {
        ++counter[byte(A[it], byteNumber)];
    }

    index[0] = 0;
    for (int it = 1; it < DIGITS; ++it) {
        index[it] = index[it - 1] + counter[it - 1];
    }

    for (int it = 0; it < N; ++it) {
        B[index[byte(A[it], byteNumber)]++] = A[it];
    }
}

void radixSort() {
    for (int it = 0; it < BYTES; ++it) {
        if (it % 2 == 0) {
            countSort(numbers, tNumbers, it);
        } else {
            countSort(tNumbers, numbers, it);
        }
    }
}

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

    scanf("%d%d%d%d", &N, &A, &B, &C);

    numbers[0] = B;
    for (int it = 1; it < N; ++it) {
        numbers[it] = ((1LL * A * numbers[it - 1] % C) + B) % C;
    }

    radixSort();

    for (int it = 0; it < N; it += 10) {
        printf("%d ", numbers[it]);
    }

    return 0;
}