Cod sursa(job #2608666)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 1 mai 2020 17:31:46
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.27 kb
//
//  main.cpp
//  radixsort
//
//  Created by Eusebiu Rares on 01/05/2020.
//  Copyright © 2020 Eusebiu Rares. All rights reserved.
//

#include <iostream>
#include "fstream"

template <typename F>
class OutputParsing {
	private :
	static const int SIZE = (1 << 20) ;
	char outBuffer[SIZE] ;
	const int BULAN = 500 ;
	int outputSize ;
	__attribute__ ( (always_inline)) int numberDigits(F x) {
		int digits = x > 999999999 ? 11 :
		x > 99999999  ? 10 :
		x > 9999999   ? 9  :
		x > 999999    ? 8  :
		x > 99999     ? 7  :
		x > 9999      ? 6  :
		x > 999       ? 5  :
		x > 99        ? 4  :
		x > 9         ? 3  : 2 ;
		return digits ;
	}
	public :
	FILE *output_file ;
	OutputParsing() {}
	OutputParsing (const char *file_name) {
		output_file = fopen (file_name, "wb") ;
		outputSize = -1 ;
	}
	__attribute__ ( (always_inline)) void sflush() {
		fwrite(outBuffer, 1, outputSize, output_file) ;
		outputSize = -1 ;
	}
	__attribute__ ( (always_inline)) void operator << (F val) {
		if (val == -1) {
			outBuffer[++ outputSize] = 45 ;
			outBuffer[++ outputSize] = 49 ;
			outBuffer[++ outputSize] = 10 ;
		} else {
			int digits = numberDigits(val) ;
			for (int i = digits ; -- i ; val /= 10) {
				outBuffer[outputSize + i] = val % 10 + 48 ;
			}
			outBuffer[outputSize = outputSize + digits] = 10 ;
		}
		if (outputSize <= SIZE - BULAN) {
			sflush() ;
		}
		return ;
	}
};

std::fstream in ("radixsort.in", std::ios::in) ;
std::fstream out ("radixsort.out", std::ios::out) ;

const int MV = 1e7 ;

int v[MV + 1] ;

namespace merge {

const int NC = 10 ;
const int BASE = 1 << 8 ;
const int BASE_IND = BASE - 1 ;
int nr[NC] ;
int aux[MV + 1] ;

void sort(int vec[], int size, int shift) {
	if (shift == 32) {
		return ;
	}
	for (int i = 0 ; i < BASE ; ++ i) {
		nr[(vec[i] >> shift) & BASE_IND] ++ ;
	}
	for (int i = 1 ; i <= BASE ; ++ i) {
		nr[i] += nr[i - 1] ;
	}
	for (int i = 0 ; i < size ; ++ i) {
		aux[nr[(vec[i] >> shift) & BASE_IND] ++] = vec[i] ;
	}
	for (int i = 0 ; i < size ; ++ i) {
		vec[i] = aux[i] ;
	}
	sort(vec, size, shift + 8) ;
}

}

int main(int argc, const char * argv[]) {
	int n, A, B, C ; in >> n >> A >> B >> C ;
	v[0] = B ;
	for (int i = 1 ; i <= n ; ++ i) {
		v[i] = (A * v[i - 1] + B) % C ;
	}
	merge::sort(v, n, 0) ;
	for (int i = 1 ; i <= n ; i = i + 10) {
		out << v[i] << ' ' ;
	}
}