Cod sursa(job #2292501)

Utilizator VadimCCurca Vadim VadimC Data 29 noiembrie 2018 17:22:41
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <fstream>

using namespace std;

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

#define NMax 10000010
#define mod (1 << 8)

int n, A, B, C;
int a[NMax];
int b[NMax], index[mod];

void citire();
void radix();
void afisare();

int main(){
	citire();
	radix();
	afisare();
}

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

void radix(){
	int i, p;
	for(p = 0; p < 32; p += 8){
		for(i = 0; i < mod; i++) index[i] = 0;
		for(i = 1; i <= n; i++) index[(a[i] >> p) & (mod - 1)]++;
		for(i = 1; i < mod; i++) index[i] += index[i - 1];
		for(i = n; i > 0; i--) b[index[(a[i] >> p) & (mod - 1)]--] = a[i];
		for(i = 1; i <= n; i++) a[i] = b[i];
	}
}

void afisare(){
	for(int i = 1; i <= n; i += 10) fout << a[i] << ' ';
}