Cod sursa(job #2900211)

Utilizator StanCatalinStanCatalin StanCatalin Data 10 mai 2022 15:19:06
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 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];
vector<int> numere[256];

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;
    for (int i=0 ;i<256; i++) {
        numere[i].clear();
    }

    for (int i=0; i<n; i++) {
        numere[get_byte(cnt, vec[i])].push_back(vec[i]);
    }
    int k = 0;
    for (int i=0; i<256; i++) {
        for (auto &y:numere[i]) {
            vec[k++] = y;
        }
    }
    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;
}