Cod sursa(job #1778152)

Utilizator BLz0rDospra Cristian BLz0r Data 13 octombrie 2016 15:50:05
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 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) {
                int x = *it;
                Radix[ind][GetVal(x, i)].push_back(x);
            }
        }
    }
    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) {
            if (p % 10 == 0)
                fout << *it << " ";
            p++;
        }
            
	return 0;
}