Pagini recente » Cod sursa (job #1609663) | Cod sursa (job #2571694) | Cod sursa (job #1882168) | Cod sursa (job #1849265) | Cod sursa (job #2634672)
#include <cstdio>
#include <vector>
FILE *fin = fopen( "radixsort.in", "r" ), *fout = fopen( "radixsort.out", "w" );
const int NumBits = 16;
const int Mask = 65535;
const int MaxN = 10000000;
const int Max10 = 10;
const int BufSz = (1 << 17);
int v[MaxN], f[Mask + 1], aux[MaxN], n;
int p10[Max10 + 1] = { 0, 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
char wbuf[BufSz];
int wpos = 0;
static inline void writeChar( char ch ) {
wbuf[wpos] = ch;
if ( !(wpos = (wpos + 1) & (BufSz - 1)) ) {
fwrite( wbuf, 1, BufSz, fout );
}
}
void writeInt( int x ) {
int i, cf;
i = Max10;
while ( p10[i] > x ) {
--i;
}
if ( i == 0 ) {
writeChar( '0' );
} else {
do {
cf = '0';
while ( p10[i] <= x ) {
x -= p10[i];
++cf;
}
writeChar( cf );
} while ( --i > 0 );
}
writeChar( ' ' );
}
static inline void flushBuf() {
fwrite( wbuf, 1, wpos, fout );
}
static inline void countSort( int step ) {
int u4, i;
for ( i = 0; i <= Mask; ++i ) {
f[i] = 0;
}
for ( i = 0; i < n; ++i ) {
u4 = ((v[i] >> (NumBits * step)) & Mask);
++f[u4];
}
for ( i = 1; i <= Mask; ++i ) {
f[i] += f[i - 1];
}
for ( i = n - 1; i >= 0; --i ) {
u4 = ((v[i] >> (NumBits * step)) & Mask);
aux[--f[u4]] = v[i];
}
for ( i = 0; i < n; ++i ) {
v[i] = aux[i];
aux[i] = 0;
}
}
int main() {
int a, b, c;
fscanf( fin, "%d%d%d%d", &n, &a, &b, &c );
v[0] = b;
for ( int i = 1; i < n; ++i ) {
v[i] = ((long long)a * v[i - 1] + b) % c;
}
countSort( 0 );
countSort( 1 );
for ( int i = 0; i < n; i += 10 ) {
writeInt( v[i] );
}
flushBuf();
fclose( fin );
fclose( fout );
return 0;
}