Cod sursa(job #2769304)

Utilizator NanuGrancea Alexandru Nanu Data 14 august 2021 16:30:01
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <cstring>

using namespace std;

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

#define DIM 10000005
#define MAX_BITS 32
#define BITS_PER_STEP 8
const int BASE = (1 << BITS_PER_STEP);  ///pentru a nu se calcula de fiecare data;
const int MASK = BASE - 1;  ///iau ultimii(bits per step) biti

int n, a, b, c, v[DIM], v1[DIM], fr[BASE], ind[BASE];

static inline void RadixSort(int v[], int v1[DIM], int n, int bits) {
    if(bits == MAX_BITS)
        return;

    ///resetez vectorul de frecvente;
    memset(fr, 0, sizeof(fr));

    int i;
    for(i = 0; i < n; i++)
        ++fr[((v[i] >> bits) & MASK)];

    ind[0] = 0;
    for(i = 1; i < BASE; i++)
        ind[i] = ind[i - 1] + fr[i - 1];

    for(i = 0; i < n; i++)
        v1[ind[((v[i] >> bits) & MASK)]++] = v[i];

    RadixSort(v1, v, n, bits + BITS_PER_STEP);

}

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

    RadixSort(v, v1, n, 0);
    for(int i = 0; i < n; i += 10)
        cout << v[i] << " ";

  return 0;
}