Cod sursa(job #2900228)

Utilizator StanCatalinStanCatalin StanCatalin Data 10 mai 2022 15:36:09
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stdlib.h>
#include <time.h>

using namespace std;

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

const int dim = 10000005;

int n, a, b, c, vec[dim], aux[dim];

int get_byte(int byte, int val) {
    int bitmask = ((1<<8) - 1);
    return ((val>>((byte-1)*8))&bitmask);
}

void Sortare(int cnt) {
    if (cnt == 5) return;
    int frecventa[256], index_fr[256];
    for (int i=0 ;i<256; i++) {
        frecventa[i] = 0;
    }

    for (int i=0; i<n; i++) {
        frecventa[get_byte(cnt, vec[i])]++;
    }
    index_fr[0] = 0;
    for (int i=1; i<256; i++) {
        index_fr[i] = index_fr[i-1] + frecventa[i-1];
    }
    int k = 0;
    for (int i=0; i<n; i++) {
        int bt = get_byte(cnt, vec[i]);
        aux[index_fr[bt]] = vec[i];
        index_fr[bt]++;
    }

    Sortare(cnt+1);
}

int main()
{
    in >> n >> a >> b >> c;
    vec[0] = b%c;
    for (int i=1; i<n; i++) {
        vec[i] = (1LL * a * vec[i-1] + b)%c;
    }
    Sortare(1);
    for (int i=0; i<n; i += 10) {
        out << vec[i] << " ";
    }
    return 0;
}