Pagini recente » Borderou de evaluare (job #125890) | Cod sursa (job #2645580) | Cod sursa (job #592852) | Monitorul de evaluare | Cod sursa (job #2756766)
#include <bits/stdc++.h>
#define uint unsigned int
#define maxn 10000000
using namespace std;
uint v[maxn][2];
int cnt[64], pref_cnt[64]; /// baza 64 <=> 6 biti
void radix_sort (int n, int &pin) {
int i, j, z, nsh;
for (i = 0; i < 5; i++, pin ^= 1) { /// fac exact 5 parcurgeri
fill(cnt, cnt+64, 0);
fill(pref_cnt, pref_cnt+64, 0);
nsh = i * 6;
for (j = 0; j < n; j++)
cnt[(v[j][pin] >> nsh) & 63]++;
for (pref_cnt[0] = cnt[0], j = 1; j < 64; j++)
pref_cnt[j] = cnt[j] + pref_cnt[j-1];
for (j = 0; j < n; j++) {
z = ((v[j][pin] >> nsh) & 63);
v[pref_cnt[z] - cnt[z]][pin^1] = v[j][pin];
cnt[z]--;
}
}
pin ^= 1;
}
int main () {
ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");
int n; fin >> n;
long long a, b, c; fin >> a >> b >> c;
v[0][0] = b;
for (int i = 1; i < n; i++) v[i][0] = (uint)((a * v[i-1][0] + b) % c);
int pin = 0;
radix_sort(n, pin);
for (int i = 0; i < n; i += 10) fout << v[i][pin] << ' ';
fout << '\n';
fin.close();
fout.close();
return 0;
}