Cod sursa(job #2550348)

Utilizator Constantin.Dragancea Constantin Constantin. Data 18 februarie 2020 18:55:26
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>
using namespace std;

vector <int> radixSort(vector <int> a, int n, int dim = 256 * 256 * 256){
    vector <int> buckets[260];
    for (int i=0; i<n; i++)
        buckets[(a[i] / dim) % 256].push_back(a[i]);
    for (int i=0; i<256; i++){
        if (buckets[i].size() < 2 || dim == 1) continue;
        buckets[i] = radixSort(buckets[i], buckets[i].size(), dim / 256);
    }
    int idx = 0;
    for (int i=0; i<256; i++){
        for (auto it: buckets[i]) a[idx++] = it;
    }
    return a;
}

int main(){
    ifstream cin ("radixsort.in");
    ofstream cout ("radixsort.out");
    int n, a, b, c;
    vector <int> v;
    cin >> n >> a >> b >> c;
    v.push_back(b);
    for (int i=1; i<n; i++) v.push_back((1LL * a * v[i-1] + b) % c);
    v = radixSort(v, n);
    for (int i=0; i<v.size(); i+=10) cout << v[i] << ' ';
    return 0;
}