Cod sursa(job #2872680)

Utilizator matthriscuMatt . matthriscu Data 17 martie 2022 17:47:07
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
	
#include <vector>
	
 
	
#define BYTE_SIZE 8
	
#define NMAX 10000000
	
 
	
using namespace std;
	
 
	
unsigned char get_nth_byte(int x, unsigned int n)
	
{
	
	return (x & ((int)(unsigned char)-1 << (n * BYTE_SIZE))) >> (n * BYTE_SIZE);
	
}
	
 
	
int main(void)
	
{
	
	ifstream fin("radixsort.in");
	
	ofstream fout("radixsort.out");
	
 
	
	int N, A, B, C;
	
	fin >> N >> A >> B >> C;
	
 
	
	int *v = new int[N];
	
	v[0] = B;
	
	for (int i = 1; i < N; ++i)
	
		v[i] = (1LL * A * v[i - 1] + B) % C;
	
	
	
	for (int byte = 0; byte < sizeof(int); ++byte) {
	
		vector<int> buckets[1 << BYTE_SIZE];
	
 
	
		for (int i = 0; i < N; ++i)
	
			buckets[get_nth_byte(v[i], byte)].push_back(v[i]);
	
 
	
		int cnt = 0;
	
		for (int i = 0; i < (1 << BYTE_SIZE); ++i)
	
			for (const int &x : buckets[i])
	
				v[cnt++] = x;
	
	}
	
 
	
	for (int i = 0; i < N; i += 10)
	
		fout << v[i] << ' ';
	
	fout << '\n';
	
 
	
	delete[] v;
	
	fin.close();
	
	fout.close();
	
	return 0;
	
}