Cod sursa(job #2649961)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 16 septembrie 2020 21:55:54
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <cstring>

using namespace std;

#define RADIX 1<<8
int counts[RADIX];
int indexes[RADIX];

void radixsort(int numbers[], int aux[], int n, int current_byte) {
    memset(counts, 0, sizeof(counts));

	for(int i=0; i<n; ++i)
		++counts[(numbers[i] >> current_byte) & 0xFF];

    indexes[0] = 0;
	for(int i=1; i< RADIX; ++i)
		indexes[i] = counts[i-1] + indexes[i-1];

	for(int i=0; i<n; ++i)
		aux[indexes[(numbers[i] >> current_byte) & 0xFF]++] = numbers[i];
}


int numbers[10000001];
int aux[10000001];


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

	int n, a, b, c, total_bytes = sizeof(numbers[0]);

	fin >> n >> a >> b >> c;
   	numbers[0] = b;
    for(int i=1; i<n; ++i)
        numbers[i] = (1LL * a * numbers[i-1] % c + b) % c;

	for(int i=0; i<total_bytes; ++i)
		if (i&1)
			radixsort(aux, numbers, n, i * 8);
		else
			radixsort(numbers, aux, n, i * 8);

	for(int i=0; i<n; i += 10)
		fout << numbers[i] << ' ';
    fout << endl;

	return 0;
}