Cod sursa(job #2551351)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 19 februarie 2020 19:29:51
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
#define ll long long	
#define ld long double
#define pii pair <int,int>	
#define x first
#define y second
#define mp make_pair

using namespace std;
	
const int Nmax = 1e7 + 5;
int v[Nmax], w[Nmax];
const int base = 256;
int fr[base], bucket[Nmax], used[base];
	
void radix_sort(const int &n){
	
	for(int bk, i, step = 0, k = 1; step < 4; k *= base, ++step){
	
		for(i = 0; i < base; ++i)
			used[i] = fr[i] = 0;

		for(i = 1; i <= n; ++i){
	
			bk = (v[i] / k) % base;
			bucket[i] = bk;
			++fr[bk];
		}
	
		for(i = 1; i < base; ++i)
			fr[i] += fr[i - 1];

		for(i = 1; i <= n; ++i){

			if(bucket[i])
				w[fr[bucket[i] - 1] + used[bucket[i]] + 1] = v[i];
			else
				w[used[0] + 1] = v[i];
			++used[bucket[i]];
		}
		for(i = 1; i <= n; ++i)
			v[i] = w[i];
	}		
}
int main(){
	
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);

    int n, a, b, c;
    cin >> n >> a >> b >> c;	
	
    v[1] = b;
    for(int i = 2; i <= n; ++i)	
    	v[i] = (1LL * (1LL * v[i - 1] * a) % c +1LL * b) % c;
		
    radix_sort(n);
	
    for(int i = 1; i <= n; i += 10)
    	cout << v[i] << ' ';

    return 0;
}