Cod sursa(job #2814385)

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

const int MAX_N = 1e7 + 5;
const int INT_BITS = 32;
const int BUCKET_BITS = 8;
const int BUCKET_SIZE = (1 << BUCKET_BITS);

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

void radixSort(unsigned int* v, const int& N){
    for(int shiftBits = 0; shiftBits < INT_BITS; shiftBits += BUCKET_BITS){
        for(int i = 0; i < N; ++i){
            int bucketIdx = (v[i] >> shiftBits) & (BUCKET_SIZE - 1);
            buckets[bucketIdx].push_back(v[i]);
        }
        int i = -1;
        for(int bucketIdx = 0; bucketIdx < BUCKET_SIZE; ++bucketIdx){
            while(!buckets[bucketIdx].empty()){
                v[++i] = buckets[bucketIdx].front();
                buckets[bucketIdx].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;
}