Cod sursa(job #1778143)

Utilizator BLz0rDospra Cristian BLz0r Data 13 octombrie 2016 15:40:40
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

#define Nmax 10000002
#define Buckets 256

#ifdef INFOARENA
ifstream fin("radix.in");
ofstream fout("radix.out");
#else
#define fin cin
#define fout cout
#endif

int GetVal(int x, int bucket) {

	int st = 8 * bucket;
	int dr = st + 8 - 1;

	int nr = 0;
	for (int i = st, j = 0; i <= dr; ++i, ++j)
		if (x & (1 << i))
			nr ^= (1 << j);

	return nr;
}

vector<int> Radix[2][Buckets];
vector<int> V;

int main(){

	int N, A, B, C;

	fin >> N >> A >> B >> C;

	V.resize(N);

	V[0] = B;

	for (int i = 1; i < N; ++i)
		V[i] = (1LL * V[i - 1] * A + B) % C;
    
    for (int i = 0; i < N; ++i)
        Radix[1][0].push_back(V[i]);
    
    #ifndef INFOARENA
    sort(V.begin(),V.end());
    for (int i = 0; i < N; ++i)
        fout << V[i] << " ";
    fout << "\n";
    #endif
    
    int ind = 0;
    for (int i = 4, ind = 0; i > 0 ; --i, ind ^= 1) {
        
        for (int j = 0; j < Buckets; ++j)
            Radix[ind][j].clear();
        
        vector<int> :: iterator it;
        for (int j = 0; j < Buckets; ++j) {
            for (it = Radix[ind^1][j].begin(); it != Radix[ind^1][j].end(); ++it)
                Radix[ind][GetVal(*it, i)].push_back(*it);
        }
    }
    ind ^= 1;
    	    
	vector<int> ::iterator it;
    
    int p = 0;
    for (int i = 0; i < Buckets; ++i)
        for (it = Radix[ind][i].begin(); it != Radix[ind][i].end(); ++it)
            V[p++] = *it;
    
    for (int i = 0; i < N; i += 10)
        fout << V[i] << " ";
	return 0;
}