Pagini recente » Cod sursa (job #2554020) | Cod sursa (job #2877470) | Cod sursa (job #55090) | Arhiva de probleme, pregatire pentru concursuri de informatica | Cod sursa (job #1501126)
#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 = byte;
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].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].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;
}