Pagini recente » Cod sursa (job #2702180) | Cod sursa (job #684276) | Cod sursa (job #428342) | Cod sursa (job #2803978) | Cod sursa (job #1226364)
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <sstream>
#include <fstream>
using namespace std;
#define MAX 10000010
#define DIG 256
ifstream f("radixsort.in");
ofstream g("radixsort.out");
int N, A, B, C, K;
unsigned int X[2][MAX], R[MAX], Count[2][DIG], Start[2][DIG], Used[DIG];
void RadixSort() {
int S = 1, D = 0, ps, pd;
unsigned int Z = 0xFF, p = 0;
for (int i = 1; i <= N; i++) {
X[1][i] = ((long long)X[1][i-1] * A + B) % C;
R[i] = X[1][i] & Z;
Count[0][R[i]]++;
}
for (int i = 1; i < DIG; i++) {
Start[0][i] = Start[0][i-1] + Count[0][i-1];
}
for (int i = 1; i <= N; i++) {
X[0][Start[0][R[i]] + Used[R[i]]] = X[1][i];
Used[R[i]]++;
}
for (int q = 1; q <= 4; q++) {
S ^= 1;
D ^= 1;
memset(Count[D], 0, sizeof(Count[D]));
memset(Start[D], 0, sizeof(Start[D]));
memset(Used, 0, sizeof(Used));
for (int j = 0; j < DIG; j++) {
for (int k = 0; k < Count[S][j]; k++) {
ps = Start[S][j] + k;
A = X[S][ps];
B = A >> p;
if (B > 0) {
R[ps] = B & Z;
Count[D][R[ps]]++;
} else {
R[ps] = -1;
if (K % 10 == 0) {
g << A << " ";
}
K++;
}
}
}
for (int i = 1; i < DIG; i++) {
Start[D][i] = Start[D][i-1] + Count[D][i-1];
}
for (int j = 0; j < DIG; j++) {
for (int k = 0; k < Count[S][j]; k++) {
ps = Start[S][j] + k;
if (R[ps] == -1) continue;
X[D][Start[D][R[ps]] + Used[R[ps]]] = X[S][ps];
Used[R[ps]]++;
}
}
p += 8;
}
for (int j = 0; j < DIG; j++) {
for (int k = 0; k < Count[D][j]; k++) {
pd = Start[D][j] + k;
if (K % 10 == 0) {
g << X[D][pd] << " ";
}
K++;
}
}
}
int main(){
f >> N >> A >> B >> C;
RadixSort();
return 0;
}