Cod sursa(job #2465818)

Utilizator Narcys01Ciovnicu Narcis Narcys01 Data 30 septembrie 2019 21:27:48
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

//#pragma warning(disable : 4996)
#define BMAX 1'000'000'001

using namespace std;

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

int a[10000007];
int tmp[10000007];
int n;

void count_sort(long long c_s)
{
	int i;
	long long count[10] = { 0 };

	for (i = 0; i < n; i++)
		count[(a[i] / c_s) % 10]++;

	for (i = 1; i < 10; i++)
		count[i] += count[i - 1]; //

	for (i = n - 1; i >= 0; i--)
	{
		count[(a[i] / c_s) % 10]--;
		tmp[count[(a[i] / c_s) % 10]] = a[i];
	}

	for (i = 0; i < n; i++)
		a[i] = tmp[i];
}

void radixSort()
{
	long long i;
	for (i = 1; i < BMAX; i *= 10)
		count_sort(i);
}


void solve()
{
	radixSort();
}

void readData()
{
	int i, A, B, C;
	fin >> n >> A >> B >> C;
	n--;
	a[0] = B;
	for (i = 1; i <= n; i++)
		a[i] = (1LL * A * a[i - 1] % C + B) % C;
}

void print()
{
	for (int i = 0; i < n; i += 10)
		fout << a[i] << " ";
}

int main()
{
//#ifndef ONLINE_JUDGE
//	freopen("date.in", "r", stdin);
//	freopen("date.out", "w", stdout);
//#endif // ONLINE_JUDGE

	readData();
	solve();
	print();

	return 0;
}