Cod sursa(job #2507319)

Utilizator catalin9898Bajenaru Catalin catalin9898 Data 9 decembrie 2019 23:25:46
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <stdio.h>
using namespace std;
int v[10000001], ma, n, aux[10000001];

void countSort(int ex)
{
    int i;
    int digits[10] = {0};
    for(i = 0; i < n; i++)
        digits[(v[i] / ex) % 10]++;
    for(i = 1; i < 10 ; i++)
        digits[i] += digits[i - 1];

    for(i = n - 1; i >= 0; i--)
    {
        aux[digits[(v[i] / ex) % 10]  - 1] = v[i];
        digits[(v[i] / ex) % 10]--;
    }
    for(i = 0; i < n; i++)
        v[i] = aux[i];

}

int main()
{
    int a, b, c,  i, w, z, ex;
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);
    scanf("%d%d%d%d",&n, &a, &b, &c);
    w = v[0] = b;
    int k = 1;
    for(i = 1 ; i < n; i++)
    {
        z = (a *1LL* w + b) % c;
        if(z > ma)
            ma = z;
    v[i] = z;
        w = z;
        //v[i] = (A * v[i-1] + B) % C
    }
    ex = 1;

    while(ma / ex > 0)
    {
        countSort(ex);
        ex *= 10;

    }

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