Cod sursa(job #2743895)

Utilizator muiepulicimatacutactu muiepulici Data 23 aprilie 2021 17:21:51
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <fstream>
 
#define BITS 4
#define BUCKETS (1 << BITS)
#define MASK ((1 << BITS) - 1)
 
void CountingSort(int* v, int n, int byte, int* temp) {
	int i;
	int count[BUCKETS] = { 0 };
 
	for (i = 0; i < n; ++i)
		++count[(v[i] >> (byte * BITS)) & MASK];
 
	for (i = 1; i < BUCKETS; ++i)
		count[i] += count[i - 1];
 
	for (i = n - 1; i >= 0; --i)
		temp[--count[(v[i] >> (byte * BITS)) & MASK]] = v[i];
}
 
void RadixSort(int* v, int n) {
	int i;
	int max = 0;
 
	for (i = 0; i < n; ++i) {
		if (v[i] > max)
			max = v[i];
	}
 
	int* temp = new int[n];
 
	for (i = 0; i < 8; ++i) {
		if (i % 2 == 0)
			CountingSort(v, n, i, temp);
		else
			CountingSort(temp, n, i, v);
	}
 
	delete[] temp;
}
 
int v[10000001];
 
int main() {
	std::ifstream fin("radixsort.in");
	std::ofstream fout("radixsort.out");
 
	int N, A, B, C;
	fin >> N >> A >> B >> C;
 
	fin.close();
 
	v[0] = B;
 
	int i;
 
	for (i = 1; i < N; ++i)
		v[i] = (1LL * A * v[i - 1] + B) % C;
 
	RadixSort(v, N);
 
	for (i = 0; i < N; i += 10)
		fout << v[i] << ' ';
	fout << '\n';
 
	fout.close();
 
	return 0;
}