Cod sursa(job #2844262)

Utilizator DanielRusuDaniel Rusu DanielRusu Data 4 februarie 2022 00:22:45
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream cin("radixsort.in");
ofstream cout("radixsort.out");

#define TOTAL_BUCKETS 2048
#define DIM 10000002

int N, nr[2][DIM], a, b, c;
int cnt[TOTAL_BUCKETS];

void reorder(int bucket, int line) {
    memset(cnt, 0, sizeof(cnt));

    for(int i = 0; i < N; i++) {
        cnt[(nr[line][i] / (1 << bucket)) % TOTAL_BUCKETS]++;
    }

    for(int i = 1; i < TOTAL_BUCKETS; i++) {
        cnt[i] += cnt[i - 1];
    }

    for(int i = N - 1; i >= 0; --i) {
        nr[1 - line][--cnt[(nr[line][i] / (1 << bucket)) % TOTAL_BUCKETS]] = nr[line][i];
    }
}

void radix() {
    for(int bucket = 0; bucket < 3; bucket++) {
        reorder(11 * bucket, bucket % 2);
    }
}

int main() {

    cin >> N >> a >> b >> c;

    nr[0][0] = b;

    for(int i = 1; i < N; i++) {

        nr[0][i] = (1LL * nr[0][i - 1] * a + b) % c;
    }

    radix();

    for(int i = 0; i < N; i += 10) {
        cout << nr[1][i] << ' ';
    }

    cout << '\n';

    return 0;
}