Pagini recente » Cod sursa (job #2414049) | Cod sursa (job #3141684) | Cod sursa (job #2423799) | Cod sursa (job #1654239) | Cod sursa (job #1501150)
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
const int NMAX = 10000001;
int N; int A; int B; int C;
int v[NMAX];
int bucket[4][NMAX];
const int byte = (1 << 8) - 1;
queue<int> Q[byte + 1];
queue<int> Qnew[byte + 1];
void read() {
fin >> N >> A >> B >> C;
v[1] = B;
//C < 2 ^ 31
for(int i = 2 ; i <= N; ++i)
v[i] = (A * v[i - 1] + B) % C;
}
void radix_sort() {
for(int i = 1; i <= N; ++i)
Q[ v[i] & byte ].push(v[i]);
int mask = 0;
for(int k = 0 ; k < 3; ++k) {
mask = mask + 8;
if(k % 2 == 0) {
for(int i = 0; i < byte + 1; ++i)
while( Q[i].empty() == false ) {
int x = Q[i].front();
Q[i].pop();
Qnew[(x >> mask) & byte ].push(x);
}
} else {
for(int i = 0; i < byte + 1; ++i)
while( Qnew[i].empty() == false ) {
int x = Qnew[i].front();
Qnew[i].pop();
Q[(x >> mask) & byte].push(x);
}
}
}
}
int main() {
read();
radix_sort();
int cnt = 0;
for(int i = 0 ; i < byte + 1; ++i)
while(Qnew[i].empty() == false) {
cnt++;
if(cnt % 10 == 1)
fout << Qnew[i].front() << " ";
Qnew[i].pop();
}
return 0;
}