Cod sursa(job #2814341)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 7 decembrie 2021 22:55:18
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <bits/stdc++.h>
using namespace std;

void radixSort(vector<int>& v){
    const int INT_BITS = 30;
    const int BUCKET_BITS = 8;
    const int BUCKET_SIZE = (1 << BUCKET_BITS);

    vector<vector<deque<int>>> buckets(2, vector<deque<int>>(BUCKET_SIZE));
    for(int num: v){
        buckets[0][num & (BUCKET_SIZE - 1)].push_back(num);
    }

    int stepIdx = 1;
    while(stepIdx * BUCKET_BITS <= INT_BITS){
        const int SHIFT_BITS = stepIdx * BUCKET_BITS;
        int previousStep = (stepIdx - 1) % 2;
        int currentStep = stepIdx % 2;
        for(int i = 0; i < BUCKET_SIZE; ++i){
            while(!buckets[previousStep][i].empty()){
                int num = buckets[previousStep][i].front();
                buckets[currentStep][(num >> SHIFT_BITS) & (BUCKET_SIZE - 1)].push_back(num);
                buckets[previousStep][i].pop_front();
            }
        }
        stepIdx += 1;
    }

    int previousStep = (stepIdx - 1) % 2;
    v.clear();
    for(int i = 0; i < BUCKET_SIZE; ++i){
        while(!buckets[previousStep][i].empty()){
            int num = buckets[previousStep][i].front();
            v.push_back(num);
            buckets[previousStep][i].pop_front();
        }
    }
}

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

    int N;
    cin >> N;

    long long A, B, C;
    cin >> A >> B >> C;

    vector<int> v(N);
    v[0] = B;
    for(int i = 1; i < N; ++i){
        v[i] = (A * v[i - 1] + B) % C;
    }

    radixSort(v);

    for(int i = 0; i < N; i += 10){
        cout << v[i] << " ";
    }

    cin.close();
    cout.close();
    return 0;
}