Pagini recente » Cod sursa (job #1478146) | Cod sursa (job #1059363) | Cod sursa (job #951418) | Cod sursa (job #680273) | Cod sursa (job #2651510)
#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] << ' ';
}