Cod sursa(job #2814376)

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

const int MAX_N = 1e7 + 5;
const int BUCKET_BITS = 8;
const int BUCKET_SIZE = (1 << BUCKET_BITS);
const int MAX_SHIFT_BITS = 24;

deque<unsigned int> buckets[2][BUCKET_SIZE];
unsigned int v[MAX_N];

void radixSort(unsigned int v[], const int& N){
    for(int i = 0; i < BUCKET_SIZE; ++i){
        buckets[0][i].clear();
        buckets[1][i].clear();
    }

    for(int i = 0; i < N; ++i){
        buckets[0][v[i] & (BUCKET_SIZE - 1)].push_back(v[i]);
    }

    int stepIdx = 1;
    while(stepIdx * BUCKET_BITS <= MAX_SHIFT_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()){
                unsigned 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;
    int idx = -1;
    for(int i = 0; i < BUCKET_SIZE; ++i){
        while(!buckets[previousStep][i].empty()){
            unsigned int& num = buckets[previousStep][i].front();
            v[++idx] = num;
            buckets[previousStep][i].pop_front();
        }
    }
}

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

    int N;
    cin >> N;

    unsigned int A, B, C;
    cin >> A >> B >> C;

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

    radixSort(v, N);

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

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