Cod sursa(job #2291250)

Utilizator VadimCCurca Vadim VadimC Data 27 noiembrie 2018 19:56:15
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;

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

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

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

void citire();
void radix_sort();
void afisare();

int main(){
	citire();
	radix_sort();
	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_sort(){
	int i, p;
	for(p = 0; p < 32; p += 16){
		for(i = 0; i < mod; i++) index[i] = 0;
		for(i = 1; i <= n; i++) index[(a[i] >> p) % mod]++;
		for(i = 1; i < mod; i++) index[i] += index[i - 1];
		for(i = n; i > 0; i--) b[index[(a[i] >> p) % mod]--] = 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] << ' ';
}