Cod sursa(job #2651510)

Utilizator vali_27Bojici Valentin vali_27 Data 22 septembrie 2020 19:38:48
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.57 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

class InParser {
private:
	FILE* fin;
	char* buffer;
	const int SIZE = 4096;
	int buffer_index;

	char get_char()
	{
		buffer_index++;
		if (buffer_index == SIZE)
		{
			size_t count = fread(buffer, 1, SIZE, fin);
			if (count < SIZE)
				buffer[count] = 0;

			buffer_index = 0;
		}

		return buffer[buffer_index];
	}
public:
	InParser(const char* name){
		fin = fopen(name, "r");
		buffer = new char[SIZE];
		memset(buffer, 0, SIZE);
		buffer_index = 0;
	}
	~InParser() {
		delete[] buffer;
		fclose(fin);
	}

	InParser& operator>>(uint32_t& nr)
	{
		char c = get_char();
		while (!isdigit(c))c = get_char();

		nr = c - '0';
		while (isdigit(c = get_char()))
			nr = nr * 10 + c - '0';
		return *this;
	}
};

class OutParser {
private:
	FILE* fout;
	char* buffer;
	const int SIZE = 4096;
	int buffer_index;
	void print_char(char c)
	{
		if (buffer_index == SIZE)
		{
			fwrite(buffer, 1, SIZE, fout);
			buffer_index = 0;
		}
		buffer[buffer_index++] = c;
	}
public:
	OutParser(const char* name){
		fout = fopen(name, "w");
		buffer = new char[SIZE];
		memset(buffer, 0, SIZE);
		buffer_index = 0;
	}
	~OutParser(){
		fwrite(buffer, 1, buffer_index, fout);
		delete[] buffer;
		fclose(fout);
	}
	OutParser& operator<<(uint32_t nr){
		if (nr < 10)
			print_char(nr + '0');
		else
		{
			(*this) << nr / 10;
			print_char(nr%10 + '0');
		}
		return *this;
	}
	OutParser& operator<<(char c){
		print_char(c);
		return *this;
	}
};


void init(std::vector<uint32_t> &nums)
{
	InParser fin("radixsort.in");
	uint32_t n, A, B, C;
	fin >> n >> A >> B >> C;
	nums.reserve(n);

	nums.push_back(B);
	for (int i = 1; i < n; ++i)
		nums.push_back((1ULL*A * nums[i - 1] + B) % C);
}

void radix_sort(std::vector<uint32_t>& nums)
{
	int count[256] = { 0 };
	std::vector<uint32_t> output;
	output.resize(nums.size());
	for (uint32_t shift = 0, step = 0; shift < 4; ++shift, step += 8)
	{
		memset(count, 0, sizeof(count));

		for (uint32_t i : nums)
			count[(i >> step) & 255]++;

		for (int i = 1; i < 256; ++i)
			count[i] += count[i - 1];

		for (int i = nums.size() - 1; i >= 0; --i)
		{
			int index = (nums[i] >> step) & 255;
			output[--count[index]] = nums[i];
		}

		for (int i = 0; i < nums.size(); ++i)
			nums[i] = output[i];
	}
}


int main()
{
	std::vector<uint32_t> nr;
	init(nr);	
	radix_sort(nr);
	
	OutParser fout("radixsort.out");

	for (int i = 0; i < nr.size(); i += 10)
		fout << nr[i] << ' ';


}