Cod sursa(job #2550356)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 18 februarie 2020 19:10:02
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 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];
const int base = 256;

void radix_sort(const int &n){

	vector <int> bucket[base];
	//bool flag = true;

	for(int bk, j, i, step = 0, k = 1; step < 4; k *= base, ++step){

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

			bk = (v[i] / k) % base;
			bucket[bk].push_back(v[i]);
		}

		j = 0;
		for(i = 0; i < base; ++i){

			for(auto &it: bucket[i])
				v[++j] = it;
			bucket[i].clear();
		}
	}
}

int main(){

	freopen("radixsort.in", "r", stdin);
	freopen("radixsort.out", "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;
}