Cod sursa(job #2881877)

Utilizator NFJJuniorIancu Ivasciuc NFJJunior Data 30 martie 2022 23:19:28
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 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;

int n, a, b, c;
int arr[Max], 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;
	}
}
int main()
{
	cin >> n >> a >> b >> c;
	arr[1] = b;
	for(int i=2;i<=n;i++)
		arr[i] = (arr[i - 1] * a + b) % c;
	RadixSort(1, n);
	for(int i=1;i<=n;i+=10)
		cout<<arr[i]<<" ";
	return 0;
}