Cod sursa(job #2626021)

Utilizator tudosemihaitudose mihai tudosemihai Data 6 iunie 2020 11:27:49
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <iostream>

using namespace std;

ifstream in ("radixsort.in");
ofstream out ("radixsort.out");

void radixSort (int *arr, int n, int base){
    int i, exp=1, maxi=arr[1];
    int arr_temp[n],rest[1024];

    for(i=1;i<=n;i++)
        maxi=max(maxi,arr[i]);

    for(i=1;i<=n;i++)
        arr_temp[i]=0;

    while(maxi/exp > 0){
        for(i=0;i<base;i++)
            rest[i]=0;
        for(i=1;i<=n;i++)
            rest[arr[i]/exp % base]++;
        for(i=1;i<base;i++)
            rest[i]=rest[i]+rest[i-1];
        for(i=n;i>=1;i--)
        {

            arr_temp[rest[arr[i]/exp % base]] = arr[i];
            rest[arr[i]/exp % base]--;
        }
        for(i=1; i<=n; i++)
            arr[i]=arr_temp[i];
        exp = exp * base;
    }

}

int v[10000001];

int main()
{
    int n,a,b,c;

    in >> n >> a >> b >> c;

    v[1]=b;

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

    radixSort(v,n,256);

    for(int i = 1; i <= n; i+=10)
    {
        out << v[i] << " ";
    }

	return 0;
}