Cod sursa(job #3175725)

Utilizator DariusHHanganu Darius DariusH Data 26 noiembrie 2023 13:02:23
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

#define N_MAX 10000000
#define BIT_MAX 32
#define BIT_GROUP 4
const int BASE = 1 << BIT_GROUP;
const int MASK = BASE - 1;

int arr1[N_MAX], auxarr[N_MAX], fq[BASE], ind[BASE];
int n;

void radixsort(int v[], int aux[], int bit) {
    if(bit == BIT_MAX) {
        return;
    }

    memset(fq, 0, sizeof(fq));

    int i;
    for(i = 0; i < n; ++i) {
        ++fq[ v[i] >> bit & MASK ];
    }

    ind[0] = 0;
    for(i = 1; i < BASE; ++i) {
        ind[i] = ind[i - 1] + fq[i - 1];
    }

    for(i = 0; i < n; ++i) {
        aux[ ind[ v[i] >> bit & MASK ]++ ] = v[i];
    }

    radixsort(aux, v, bit + BIT_GROUP);
}

int main()
{
    int a, b, c, i;
    fin >> n >> a >> b >> c;
    arr1[0] = b;
    for(i = 1; i < n; ++i) {
        arr1[i] = (1LL * a * arr1[i - 1] + b) % c;
    }
    radixsort(arr1, auxarr, 0);

    for(i = 0; i < n; i += 10) {
        fout << arr1[i] << ' ';
    }


    return 0;
}