Cod sursa(job #2551400)

Utilizator Data 19 februarie 2020 19:59:57 Radix Sort 70 cpp-64 done Arhiva educationala 1.02 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 + 1), used(base + 1), w(v.size());

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

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

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

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

for(auto &it:v){

int buk = ((it >> bk) & (base - 1)) + 1;
w[fr[buk - 1] + used[buk]] = it;
++used[buk];
}

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;
}``````