Cod sursa(job #2640116)

Utilizator dahaandreiDaha Andrei Codrin dahaandrei Data 5 august 2020 11:40:52
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.27 kb
#include <bits/stdc++.h>

using namespace std;

#define lli long long int
class OutParser {
	
private:
	
    FILE *fout;
	
    char *buff;
	
    int sp;
	
    void write_ch(char ch) {
	
        if (sp == 50000) {
	
            fwrite(buff, 1, 50000, fout);
	
            sp = 0;
	
            buff[sp++] = ch;
	
        } else {
	
            buff[sp++] = ch;
	
        }
	
    }
	
public:
	
    OutParser(const char* name) {
	
        fout = fopen(name, "w");
	
        buff = new char[50000]();
	
        sp = 0;
	
    }
	
    ~OutParser() {
	
        fwrite(buff, 1, sp, fout);
	
        fclose(fout);
	
    }
	
    OutParser& operator << (int vu32) {
	
        if (vu32 <= 9) {
	
            write_ch(vu32 + '0');
	
        } else {
	
            (*this) << (vu32 / 10);
	
            write_ch(vu32 % 10 + '0');
	
        }
	
        return *this;
	
    }
	
    OutParser& operator << (char ch) {
	
        write_ch(ch);
	
        return *this;
	
    }
	
    OutParser& operator << (const char *ch) {
	
        while (*ch) {
	
            write_ch(*ch);
	
            ++ch;
	
        }
	
        return *this;
	
    }
	
};

ifstream in("radixsort.in");
OutParser out("radixsort.out");

const int MAXN = 1e7;
const int chunkSize = 8;
const int chunkCnt = 32 / chunkSize;

int n;
vector<int> v;

void read() {
	int a, b, c;
	in >> n >> a >> b >> c;
	v.resize(n);

	v[0] = b;
	for (int i = 1; i < n; ++ i)
		v[i] = (1LL * a * v[i - 1] + b) % c;
}

vector<int> result;
void countSort(vector<int> &nums, int chunk) {
	vector<int> index(1 << chunkSize), count(1 << chunkSize);

	for (auto &x : nums)
		++ count[(x >> (chunkSize * chunk)) & 0xFF];
	
	index[0] = 0;
	for (int i = 1; i < index.size(); ++ i)
		index[i] = index[i - 1] + count[i - 1];

	result.clear();
	result.resize(nums.size());
	for (auto &x : nums)
		result[index[(x >> (chunkSize * chunk)) & 0xFF] ++] = x;

	nums = result;
}

void radixSort() {
	for (int i = 0; i < chunkCnt; ++ i)
		countSort(v, i);
}

void writeAns() {
	for (int i = 0; i < v.size(); i += 10)
		out << v[i] << ' ';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	read();
	radixSort();
	writeAns();

	return 0;
}