Cod sursa(job #2769290)

Utilizator NanuGrancea Alexandru Nanu Data 14 august 2021 15:54:55
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <vector>

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

vector<int> bucket[BASE];
int n, a, b, c, v[DIM];

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

    int i;
    for(i = 1; i <= n; i++)
        bucket[((v[i] >> bits) & MASK)].push_back(v[i]);   ///retin elementul in galeata corespunzatoare;

    i = 0;
    for(int b = 0; b < BASE; b++) {
        for(unsigned int j = 0; j < bucket[b].size(); j++)
            v[++i] = bucket[b][j];
        bucket[b].clear();
    }

    RadixSort(v, n, bits + BITS_PER_STEP);

}

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

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

  return 0;
}