Cod sursa(job #2871780)

Utilizator AACthAirinei Andrei Cristian AACth Data 15 martie 2022 18:24:33
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");
#define cin f
#define cout g
const int Max = 1e7 + 1;
void nos()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
	
int n,a,b,c;
void read()
{
    f>>n>>a>>b>>c;
}
void solve()
{
    
}
void restart()
{

}
int arr[Max];
int aux[Max];
int get_max(int left, int right)
{
	int mx = arr[left];
	for(int i=left;i<=right;i++)
		mx = max(mx, arr[i]);
	return mx;
}
void countSort(int left, int right, int exp)
{
	const int base = (1 << 16);
	int poz[base] = {};
	for(int i=left;i<=right;i++)
		poz[arr[i] / exp % base] ++;
	for(int i=1;i<base;i++)
		poz[i] += poz[i - 1];
	for(int i=right;i>=left;i--)
	{
		aux[poz[arr[i] / exp % base]] = arr[i];
		poz[arr[i] / exp % base] --;
	}
	for(int i=left;i<=right;i++)
		arr[i] = aux[i];
}
void RadixSort(int left, int right)
{
	const int base = (1 << 16);
	int mx = get_max(left, right);
	for(int exp = 1 ; mx / exp > 0 ; exp *= base)
	{
		countSort(left, right, exp);
		if(exp == base)
			break;
	}
}
int32_t main()
{
    nos();
    read();
    int i;
    arr[1] = b;
    for(i=2; i<=n; i++)
        arr[i] = (1LL*a*arr[i-1] + b) % c;
    RadixSort(1,n);
    for(i=1;i<=n;i+=10)
    	g << arr[i] <<' ';

    
    return 0;
}