Cod sursa(job #1774600)

Utilizator nurof3nCioc Alex-Andrei nurof3n Data 9 octombrie 2016 10:41:59
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;
ifstream f ("radixsort.in");
ofstream g ("radixsort.out");
int n, a[10000001], v[10000001], A, B, C;
void afisare (int a[], int n)
{
    for (int i = 1; i <= n; i += 10)
    {
        g << a[i] << ' ';
    }
}
int getmax (int a[], int n)
{
    int mx = 0;
    for (int i = 1; i <= n; i++)
        if (a[i] > mx)
        {
            mx = a[i];
        }
    return mx;
}
void countsort (int a[], int n, int cf)
{
    int ap[10];
    for (int i = 0; i < 10; i++)
        ap[i] = 0;
    for (int i = 1; i <= n; i++)
        ap[ (a[i] / cf) % 10]++;
    ///
    for (int i = 1; i < 10; i++)
        ap[i] += ap[i - 1];
    ///ACUM IN AP[i] SE RETINE POZITIA IN SIRUL SORTAT
    for (int i = n; i >= 1; i--)
    {
        int x = (a[i] / cf) % 10;
        v[ap[x]] = a[i];
        ap[x]--;
    }
    for (int i = 1; i <= n; i++)
        a[i] = v[i];
}
void radixsort (int a[], int n)
{
    int MAX = getmax (a, n);
    for (int cf1 = 1; MAX / cf1 > 0; cf1 *= 10)
    {
        countsort (a, n, cf1);
    }
}
int main()
{
    f >> n >> A >> B >> C;
    a[1] = B;
    for (int i = 2; i <= n; i++)
    {
        a[i] = (1LL*A * a[i - 1] + B) % C;
    }
    radixsort (a, n);
    afisare (a, n);
    return 0;
}