Cod sursa(job #2550297)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 18 februarie 2020 18:12:05
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 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){

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

	for(int bk, j, i, k = 1; ; k *= base){

		for(int i = 0; i < base; ++i)
			bucket[i].clear();
		flag = false;

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

			bk = (v[i] / k) % base;

			if(v[i] / k)
				flag = true;

			bucket[bk].push_back(v[i]);
		}

		if(!flag) break;

		j = 0;
		for(i = 0; i < base; ++i)
			for(auto &it: bucket[i])
				v[++j] = it;
	}
}

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] = ((v[i - 1] * a) % c + b) % c;
    
    radix_sort(n);

    for(int i = 1; i <= n; i += 10)
    	cout << v[i] << ' ';
    
    return 0;
}