Cod sursa(job #2551410)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 19 februarie 2020 20:07:03
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 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;
const int base = 256;
vector <int> v;
	
void radix_sort(){

	vector <int> fr(base), w(v.size());

	for(int bk = 0; bk < 32; bk += 8){

		fill(fr.begin(), fr.end(), 0);

		for(auto &it:v)
			++fr[(it >> bk) & (base - 1)];

		for(int i = 1; i <= base; ++i)
			fr[i] += fr[i - 1];

		for(int i = v.size() - 1; i >= 0; --i)
			w[--fr[(v[i] >> bk) & (base - 1)]] = v[i];

		v = w;
	}
}
int main(){
	
	freopen("radixsort.in", "r", stdin);
	freopen("radixsort.out", "w", stdout);

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

    return 0;
}