Cod sursa(job #2304924)

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

#define lli long long
#define N 10000001

using namespace std;
int v[N], aux[N];
int n, A, B, C, maxx = INT_MIN;

void countingSort(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(int maxx)
{
    int multip = 1;
    while(maxx){
        countingSort(multip);
        multip *= 10;
        maxx /= 10;
    }
}

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

    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(maxx);

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

    return 0;
}