Cod sursa(job #2439413)

Utilizator ShayTeodor Matei Shay Data 15 iulie 2019 20:17:18
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <stdio.h>
#include <string.h>

#define RADIX 0xFF
#define RADIX_SIZE 1 << 8
#define NMAX 10000005

int n, v[NMAX], count[RADIX_SIZE], temp[NMAX], byte;

inline int read() {
    int n = 0;
    char c = getchar_unlocked();

    while (!('0' <= c && c <= '9')) {
        c = getchar_unlocked();
    }

    while ('0' <= c && c <= '9') {
        n = n * 10 + c - '0';
        c = getchar_unlocked();
    }

    return n;
}

inline void print(int n) {
    char snum[65];
    int i = 0;

    do {
        snum[i++] = n % 10 + '0';
        n /= 10;
    } while (n);

    --i;

    while (i >= 0) {
        putchar(snum[i--]);
    }

    putchar(' ');
}

inline int get_byte(int x, int byte) {
    return (x >> (byte * 8)) & RADIX;   
}

inline void counting_sort() {
    memset(count, 0, sizeof(count));

    for (int i = 0 ; i < n ; ++i) {
        count[get_byte(v[i], byte)]++;
    }

    for (int i = 1 ; i <= RADIX ; ++i) {
        count[i] += count[i - 1];
    }

    for (int i = n - 1; i >= 0 ; --i) {
        temp[--count[get_byte(v[i], byte)]] = v[i];
    }

    for (int i = 0 ; i < n ; ++i) {
        v[i] = temp[i];
    }
}

inline void radix_sort() {
    for (; byte < 4 ; ++byte) {
        counting_sort();
    }
}

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

    int a, b, c;
    n = read(), a = read(), b = read(), c = read();
    v[0] = b % c;

    for (int i = 1 ; i < n ; ++i) {
        v[i] = (1LL * a * v[i - 1] + b) % c;
    }

    radix_sort();

    for (int i = 0 ; i < n ; i += 10) {
        print(v[i]);
    }

    return 0;
}