Cod sursa(job #1179328)

Utilizator DuxarFII-Stefan-Negrus Duxar Data 28 aprilie 2014 14:20:53
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.31 kb
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <cstdio>
#include <stack>
#include <algorithm>
#include <list>
#include <bitset>
#include <ctime>
#include <cassert>
#include <iomanip>

using namespace std;

//```
#define ONLINE_JUDGE

const string file = "radixsort";
const string inputF = file + ".in";
const string outputF = file + ".out";

const double epsilon = 1e-7;
#define LL long long
#define ULL unsigned long long 
#define MOD1 666013
#define MOD2 666019
#define MOD3 1999999973
#define base 73

typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<string> vs;
typedef pair<int, int> ii;
typedef pair<long long, long long> ll;
typedef vector<ii> vii;
typedef vector<ll> vll;

#define all(V) V.begin(), V.end()
#define allr(V) V.rbegin(), V.rend()
#define for_c_it(container, it) for (auto it : container)
#define present(container, element) (container.find(element) != container.end()) 
#define sz(a) int((a).size()) 
#define pb push_back 
#define mp make_pair
#define zeroes(x) ((x ^ (x - 1)) & x)
#define printC(C) for (auto x:C) { cout << x << ' '; } cout << '\n';
int N, A, B, C;
vi V, fr(2), TT;


void solve(vi &V, vi &TT, int &p) {
	int i;
	for (i = N - 1; i >= 0; --i) {
		if ((V[i] & p) != 0) {
			++fr[1];
		}
		else {
			++fr[0];
		}
	}		
	fr[1] += fr[0];
	for (i = N - 1; i >= 0; -- i) {
		if ((V[i] & p) != 0) {
			TT[fr[1] - 1] = V[i];
			--fr[1];
		}
		else {
			TT[fr[0] - 1] = V[i];
			--fr[0];
		}
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#else 
	freopen(inputF.c_str(), "r", stdin);
	freopen(outputF.c_str(), "w", stdout);
#endif

	int mx, i, p = 1, st = 1;

	scanf("%d %d %d %d", &N, &A, &B, &C);
	V.resize(N);
	TT.resize(N);
	
	mx = V[0] = B;
	for (i = 1; i < N; ++i) {
		V[i] = (A * V[i - 1] + B) % C;
		mx = max(V[i], mx);
	}
	
	while (p <= mx) {
		fr[0] = fr[1] = 0;
		if (st == 1) {
			solve(V, TT, p);
//printC(TT);
		}
		else {
			solve(TT, V, p);
//printC(V);
		}

		st = 1 - st;
		p <<= 1;
	}
	if (st == 1) {
		for (i = 0; i < N; i += 10) {
			printf("%d ", V[i]);
		}
	}
	else {
		for (i = 0; i < N; i += 10) {
			printf("%d ", TT[i]);
		}
	}
	

	return 0;
}