Cod sursa(job #2241544)

Utilizator Bulboaca_EugenBulboaca Alexandru Eugen Bulboaca_Eugen Data 16 septembrie 2018 12:12:54
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
using namespace std;
long long v[10000001], n, A, B, C;
long long ordonat[10000001];
int countingSort[1 << 16];

ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

void citire(){
    fin >> n >> A >> B >> C;
    v[1] = B;
    for(int i = 2; i <= n; ++i){
        v[i] = (1LL * A * v[i-1] + B) % C;
    }
}

void radixSort(int bucketSize, int whichBucket){
    int constant = 1 << bucketSize, mask = (1 << bucketSize) - 1;
    for(int i = 0; i < constant; ++i) countingSort[i] = 0;
    for(int i = 1; i <= n; ++i){
        long long current_value = (v[i] >> (bucketSize * whichBucket)) & mask;
        countingSort[current_value] ++;
    }
    for(int i = 1; i < constant; ++i) countingSort[i] += countingSort[i - 1];
    for(int i = n; i >= 1; --i){
        long long current_value = (v[i] >> (bucketSize * whichBucket)) & mask;
        ordonat[countingSort[current_value]] = v[i];
        countingSort[current_value]--;
    }
    for(int i = 1; i <= n; ++i) v[i] = ordonat[i];
}
void afisare(){
    for(int i = 1; i <= n; i += 10) fout << v[i] << " ";
}
int main()
{
    citire();
    for(int i = 0; i < 2; ++i) radixSort(16, i);
    afisare();
    return 0;
}