Cod sursa(job #2355682)

Utilizator maria_sinteaMaria Sintea maria_sintea Data 26 februarie 2019 11:25:42
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <cstring>
#include <cstdio>
#define N 10000005
#define M 256

using namespace std;

int n, a, b, c, v[N], m, nr[M], out[N];

void generare()
{
    v[1]=b;
    for(int i=2;i<=n;i++)
    {
        v[i]=(1LL*a*v[i-1]+b)%c;
        if(m<v[i])
            m=v[i];
    }
}

void countsort(int exp)
{
    memset(nr, 0, sizeof(nr));
    for(int i=1;i<=n;i++)
        nr[(v[i]/exp)%10]++;
    for(int i=1;i<10;i++)
        nr[i]+=nr[i-1];
    for(int i=n;i>=1;i--)
    {
        out[nr[(v[i]/exp)%10]]=v[i];
        nr[(v[i]/exp)%10]--;
    }
    for(int i=1;i<=n;i++)
        v[i]=out[i];
}

void sortare()
{
    for(int exp=1;m/exp>0;exp=exp*10)
        countsort(exp);
}

void afisare()
{
    for(int i=1;i<=n;i+=10)
        printf("%d ", v[i]);
}

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

    scanf("%d %d %d %d\n", &n, &a, &b, &c);
    generare();
    sortare();
    afisare();
    return 0;
}