Cod sursa(job #2304920)

Utilizator Salamandra01Felmeri Zsolt Salamandra01 Data 18 decembrie 2018 20:16:25
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <climits>

#define lli long long

using namespace std;
lli *v;
lli N, A, B, C, maxx = LONG_MIN;

void countingSort(lli aux[], int szj)
{
    int digits[10] = {0};

    for(int i = 0; i < N; ++i){
        digits[(v[i] / szj) % 10]++;
    }
    for(int i = 1; i < 10; ++i){
        digits[i] += digits[i-1];
    }

    for(int i = N-1; i >= 0; --i){
        aux[digits[(v[i] / szj) %10] - 1] = v[i];
        digits[(v[i] / szj) % 10]--;
    }

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

void radixSort(lli aux[], int maxx)
{
    int multip = 1;
    while(maxx){
        countingSort(aux, multip);
        multip *= 10;
        maxx /= 10;
    }
}

int main()
{
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);
    lli *aux;
    int k = 0;
    scanf("%lld%lld%lld%lld", &N, &A, &B, &C);

    v = (lli*)malloc((N+3) * sizeof(lli));
    aux = (lli*)malloc((N+3) * sizeof(lli));
    v[0] = B;
    for(int i = 1; i < N; ++i){
        v[i] = (A * v[i-1] + B) % C;
    }

    for(int i = 0; i < N; ++i){
        if(maxx < v[i]){
            maxx = v[i];
        }
    }

    radixSort(aux, maxx);

    for(int i = 0; i < N && k < 10; i += 10){
        printf("%lld ", v[i]);
        k++;
    }
    printf("\n");

    return 0;
}