Cod sursa(job #2606317)

Utilizator leeviiTempfli Levente2 leevii Data 27 aprilie 2020 15:19:20
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
	
#include <iostream>
	
#include <sstream>
	
#include <vector>
	
#include <cstring>
	
 
	
 
	
using namespace std;
	
 
	
ifstream fin("radixsort.in");
	
ofstream fout("radixsort.out");
	
 
	
#define RADIX 0xFF
	
 
	
#define RADIX_SIZE 8
	
 
	
#define TOTAL_BYTES sizeof(numbers[0])
	
 
	
int n;
	
 
	
int numbers[10000001];
	
 
	
int get_byte(int d, int byte) {
	
	return ((d >> (byte * 8))&RADIX);
	
}
	
 
	
void countsort(int A[], int B[], int byte) {
	
	int counter[1 << RADIX_SIZE];
	
	int index[1 << RADIX_SIZE];
	
 
	
	memset(counter, 0, sizeof(counter));
	
 
	
	for (int i = 0; i < n; i++)
	
		++counter[get_byte(A[i],byte)];
	
 
	
	index[0] = 0;
	
	for (int i = 1; i < 1 << RADIX_SIZE; i++)
	
		index[i] = index[i - 1] + counter[i - 1];
	
 
	
	for (int i = 0; i < n; i++)
	
		B[index[get_byte(A[i],byte)]++] = A[i];
	
 
	
}
	
 
	
void radixsort() {
	
	int *temp = new int[n];
	
	for (int i = 0; i < TOTAL_BYTES; i++) {
	
		if (i % 2 == 0)
	
			countsort(numbers, temp, i);
	
		else
	
			countsort(temp, numbers, i);
	
	}
	
 
	
}
	
 
	
void read(){
	
	int a, b, c;
	
	fin >> n >> a >> b >> c;
	
	numbers[0] = b % c;
	
	for (int i = 1; i < n; i++)
	
		numbers[i] = (1LL * a * numbers[i - 1] % c + b) % c;
	
 
	
}
	
 
	
void write(){
	
	for (int i = 0; i < n; i += 10)
	
		fout << numbers[i] << ' ';
	
 
	
}
	
 
	
 
	
 
	
int main(){
	
	read();
	
	radixsort();
	
	write();
	
	return 0;
	
 
	
}