Pagini recente » Cod sursa (job #336102) | Cod sursa (job #2940760) | Cod sursa (job #104104) | Rating Precup Laura Maria (laura09) | Cod sursa (job #1189896)
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define MAXN 10000002
#define TOTAL_BYTES 4
#define RADIX_SIZE 8
int N;
int V[MAXN];
int count[10];
int getByteMy(int x, int i) {
return (x >> (i * 8)) & (0xFF);
}
void countSort(int V[], int res[], int poz) {
int count[ 1 << RADIX_SIZE];
memset(count, 0, sizeof (count));
for (int i = 0; i < N; i++) {
int val = getByteMy(V[i], poz);
count[val]++;
}
int index[1 << RADIX_SIZE];
memset(index, 0, sizeof (index));
// cum sum
index[0] = count[0];
for (int i = 1; i < 1 << RADIX_SIZE; i++) {
index[i] = index[i - 1] + count[i];
}
for (int i = N - 1; i >= 0; i--) {
int byte = getByteMy(V[i], poz);
index[byte]--;
res[index[byte]] = V[i];
}
}
void radixSort() {
int* temp = new int[N];
for (int i = 0; i < TOTAL_BYTES; i++) {
if (i % 2 == 0) {
countSort(V, temp, i);
} else {
countSort(temp, V, i);
}
}
}
int main() {
freopen("radixsort.in", "r", stdin);
freopen("radixsort.out", "w", stdout);
int A, B, C;
cin >> N >> A >> B >> C;
V[0] = B;
for (int i = 1; i < N; i++) {
V[i] = (1ll * A * V[i - 1] % C + B) % C;
}
// cout << getByteMy(2, 0) << " ";
// cout << getByteMy(V[1], 0) << " ";
// cout << getByte(511, 0);
radixSort();
for (int i = 0; i < N; i = i + 10) {
cout << V[i] << " ";
}
cout << endl;
fclose(stdin);
fclose(stdout);
return 0;
}