Cod sursa(job #3348136)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 19 martie 2026 21:39:50
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;

#define USE_STD_IO 0
#if USE_STD_IO
    #define fin cin
    #define fout cout
#else
    ifstream fin("radixsort.in");
    ofstream fout("radixsort.out");
#endif // USE_STD_IO

const int MAX = 10000002;
const int UP = (1 << 8) - 1;
int n, a, b, c, i, put;
int vv[MAX + 2];
int v[MAX + 2];
int fr[302];

int main() {
    if(USE_STD_IO) ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

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

    put = 1;
    for(int iter = 1; iter <= 4; iter++) {
        for(i = 0; i <= UP; i++) fr[i] = 0;

        for(i = 1; i <= n; i++) {
            fr[v[i] >> put & UP]++;
        }

        for(i = 1; i <= UP; i++) {
            fr[i] += fr[i - 1];
        }

        for(i = n; i >= 1; i--) {
            vv[fr[v[i] >> put & UP]--] = v[i];
        }

        for(i = 1; i <= n; i++) v[i] = vv[i];
        put <<= 8;
    }
    for(i = 1; i <= n; i += 10) fout << v[i] << ' ';

    return 0;
}