Cod sursa(job #2669013)

Utilizator H7GhosTsdfgsd asdf H7GhosT Data 5 noiembrie 2020 21:27:08
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>
using namespace std;


int main() {
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);
    const int BASE = 256;
    int count[BASE]{};

    int n, a, b, c;
    scanf("%d%d%d%d", &n, &a, &b, &c);
    int *v = new int[n];
    int *container = new int[n];

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

    auto dig = [] (int val, int sh) {
        return (val >> (sh * 8)) & (BASE -1);
    };
    for (int sh = 0; sh < 4; sh++) {
        memset(count, 0, sizeof(count));
        for (int i = 0; i < n; i++) {
            count[dig(v[i], sh)]++;
        }
        int pref = 0;
        for (int i = 0; i < BASE; i++) {
            int tmp = count[i];
            count[i] = pref;
            pref += tmp;
        }
        for (int i = 0; i < n; i++) {
            container[count[dig(v[i], sh)]++] = v[i];
        }
        int* tmp = container;
        container = v;
        v = tmp;
    }
    for (int i = 0; i < n; i += 10) {
        printf("%d ", v[i]);
    }
    puts("");
}