Cod sursa(job #2439403)

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

#define RADIX 0xFF
#define NMAX 10000005 
int n, v[NMAX], count[RADIX], 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 << 3) + (n << 1) + 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(' ');
}

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

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 <= 0xFF ; ++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];
    }
}

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;
}