Cod sursa(job #1882803)

Utilizator 1475369147896537415369Andrei Udriste 1475369147896537415369 Data 17 februarie 2017 15:05:30
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
#include <queue>
using namespace std;

int N, A, B, C, v[10000000];

void RadixSort(int v[], int left, int right){
    queue<int> bucket[10];
    int exponent = 1, remainder, maxDigits = 10;

    for(j = 1; j <= maxDigits; j++){
        for(int i = left; i <= right; i++){
            remainder = v[i] / exponent % 10;
            bucket[remainder].push(v[i]);
        }int index = -1;

        for(int i = 0; i < 10; i++){
            while(!bucket[i].empty()){
                v[++index] = bucket[i].front();
                bucket[i].pop();
            }
        }exponent *= 10;
    }
}

int main(){

freopen("radixsort.in", "r", stdin);
freopen("radixsort.out", "w", stdout);

scanf("%d %d %d %d", &N, &A, &B, &C);

v[0] = B;

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

for(int i = 0; i < N; i+= 10){
    printf("%d ", v[i]);
}
return 0;
}