Cod sursa(job #3328203)

Utilizator Seba1030Banescu Stefan Sebastian Seba1030 Data 6 decembrie 2025 20:32:54
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include<bits/stdc++.h>

const int MAXN = 10000000;
const int MAX_BITS = 32;
const int BITS_PER_STEP = 4;
const int BASE = 1 << BITS_PER_STEP;
const int MASK = BASE - 1;

using namespace std;

int v2[MAXN];
int freq[BASE], ind[BASE];

void rdxsort( int v[], int aux[], int n, int bits ) {
    if (bits == MAX_BITS)
        return;
    memset(freq, 0, sizeof(freq));
    int i;
    for (i = 0; i < n; ++i)
        ++freq[v[i] >> bits & MASK];
    ind[0] = 0;
    for (i = 1; i < BASE; ++i)
    ind[i] = ind[i - 1] + freq[i - 1];
    for (i = 0; i < n; ++i)
        aux[ind[v[i] >> bits & MASK]++] = v[i];
    rdxsort(aux, v, n, bits + BITS_PER_STEP);
} 

int v[MAXN + 5];

int main() {
    ifstream cin( "radixsort.in" );
    ofstream cout( "radixsort.out" );
    ios::sync_with_stdio ( false );
    cin.tie ( nullptr );
    unsigned int n, a, b, c;
    cin >> n >> a >> b >> c;
    v[0] = b;
    for ( unsigned int i = 1; i < n; i++ ) {
        v[i] = ( a * v[i - 1] + b ) % c;
    }
    rdxsort ( v, v2, n, 0 );
    for ( unsigned int i = 0; i < n; i += 10 ) {
        cout << v[i] << " ";
    }

    return 0;
}