Cod sursa(job #1401924)

Utilizator irimiecIrimie Catalin irimiec Data 26 martie 2015 10:58:20
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <bits/stdc++.h>

using namespace std;

#define     mp              make_pair
#define     fs              first
#define     sc              second
#define     pob             pop_back
#define     pub             push_back
#define     eps             1E-7
#define     sz(a)           a.size()
#define     count_one       __builtin_popcount;
#define     count_onell     __builtin_popcountll;
#define     fastIO          ios_base::sync_with_stdio(false)
#define     PI              (acos(-1.0))
#define     linf            (1LL<<62)//>4e18
#define     inf             (0x7f7f7f7f)//>2e9

#define MAXN 10000002

int n, a, b, c;
int v[MAXN];

int comp (const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

#define BASE 4
void radix(int* nums, int length, int max) {
	list<int> bucket[BASE];
	int i;

	for (int n=1; max >= n; n *= BASE) {
		for (i=0; i<length; i++)
			bucket[(nums[i]/n)%BASE].push_back(nums[i]);

		for (int k=i=0; i<BASE; bucket[i++].clear())
			for (list<int>::iterator j = bucket[i].begin(); j != bucket[i].end(); nums[k++] = *(j++));
	}
}

void read() {
    #ifndef ONLINE_JUDGE
    assert(freopen("radixsort.in", "r", stdin));
    assert(freopen("radixsort.out", "w", stdout));
    #endif

	assert(scanf("%d%d%d%d", &n, &a, &b, &c));
	v[1] = b;
	int maxn = b;
	for(int i = 2; i <= n; ++i) {
        v[i] = (1LL * a * v[i-1] + b) % c;
        if(v[i] > maxn)
            maxn = v[i];
	}

    radix(v, n, maxn);
    for(int i = 1; i <= n; i += 10)
        printf("%d ", v[i]);
}

int main() {
	read();

    return 0;
}