# Cod sursa(job #2550628)

Utilizator Data 18 februarie 2020 22:04:49 Radix Sort 0 cpp-64 done Arhiva educationala 1.09 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;

void radix_sort(const int &n){

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

for(i = 0; i < base; ++i)
fr[i] = bucket[i] = used[i] = 0;

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

bk = (v[i] / k) % base;
bucket[i] = bk;
++fr[bk];
}

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

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

w[fr[bucket[i] - 1] + used[bucket[i]] + 1] = v[i];
++used[bucket[i]];
}

for(i = 1; i <= n; ++i)
v[i] = w[i];
}
}

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;

}``````