Cod sursa(job #2600945)

Utilizator Groza_Iulia_DianaGroza Iulia Diana Groza_Iulia_Diana Data 13 aprilie 2020 14:45:54
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#define nMax 10000005
typedef long long ll;

using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

void countSort(ll v[], int n, int i)
{
	ll aux[n];
	int fr[10]={0};
	for(int j=0; j<n; j++)
		fr[(v[j]/i)%10]++;
	for(int j=1; j<10; j++)
		fr[j]+=fr[j-1];
	for(int j=n-1; j>=0; j--)
	{
		aux[fr[(v[j]/i)%10]-1]=v[j];
		fr[(v[j]/i)%10]--;
	}
	for(int j=0; j<n; j++)
		v[j]=aux[j];
}

void radixSort(ll v[], int n)
{
    ll Max=v[0];
    for(int i=1; i<n; i++)
        Max=max(Max, v[i]);
    for(int i=1; Max/i>0; i*=10)
        countSort(v, n, i);
}

int main()
{
    int n, a, b, c;
    fin >> n >> a >> b >> c;
    ll v[n];
    v[0]=b;
    for(int i=1; i<n; i++)
        v[i]=(a*v[i-1]+b)%c;
    radixSort(v, n);
    for(int i=0; i<n; i+=10)
        fout << v[i] << ' ';
    return 0;
}