Cod sursa(job #2271340)

Utilizator marian013Giugioiu Marian Constantin marian013 Data 28 octombrie 2018 13:46:25
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include<stdio.h>
using namespace std;
int n, v[10000002], r[10000002], sf[10];
int getMax()
{
    int mx = v[0];
    for (int i = 1; i < n; i++)
        if (v[i] > mx)
            mx = v[i];
    return mx;
}
void countsort(int exp){
    int i;
    for(i = 0; i < n; i++)
        ++sf[v[i] / exp % 10];
    for (i = 1; i < 10; i++)
        sf[i] += sf[i - 1];
    for (i = n - 1; i >= 0; i--)
    {
        r[sf[v[i]/exp%10] - 1] = v[i];
        sf[(v[i]/exp)%10]--;
    }
    for (i = 0; i < n; i++)
       v[i] = r[i];
    for(i=0;i<10;i++)
        sf[i]=0;
}
void radixsort(){
    int m = getMax();
    for (int exp = 1; m/exp > 0; exp *= 10)
        countsort(exp);
}
int main()
{
    int a, b, c, i;
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);
    scanf("%d%d%d%d",&n,&a,&b,&c);
    v[0] = b % c;
    for(i = 1; i < n; i++)
        v[i] = (1ll * a * v[i-1] % c + b) % c;
    radixsort();
    for(i = 0; i < n; i+=10)
    printf("%d ",v[i]);
}