Cod sursa(job #1348172)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 19 februarie 2015 15:51:34
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>

using namespace std;

#define IN_FILE "radixsort.in"
#define OUT_FILE "radixsort.out"
#define MAX_N 10000000

int N, v[ MAX_N ];
inline void rad( int *v, int *tmp, const int &byte ) {
    int c[ 1 << 8 ] = { }, r[ 1 << 8 ];
    for( register int i = 0; i != N; ++i )
        ++c[ ( v[ i ] >> ( byte << 3 ) ) & 0xFF ];
    *r = 0;
    for( register int i = 1; i != 256; ++i )
        r[ i ] = r[ i - 1 ] + c[ i - 1 ];
    for( register int i = 0; i != N; ++i )
        tmp[ r[ ( v[ i ] >> ( byte << 3 ) ) & 0xFF ]++ ] = v[ i ];
}
inline void radix( ) {
    int *aux = new int [ N ];
    for( register int i = 0; i < 4; ++i )
        if( i & 1 )
            rad( aux, v, i );
        else
            rad( v, aux, i );
}
int main( ) {
    fstream f;
    int A, B, C;

    f.open( IN_FILE, ios :: in );
    f >> N >> A >> B >> C;
    f.close( );
    *v = B;
    for( int i = 1; i != N; ++i )
        v[ i ] = ( static_cast < long long > ( A * v[ i - 1 ] ) % C + B ) % C;
    radix( );
    f.open( OUT_FILE, ios :: out );
    for( int i = 0; i != N; i += 10 )
        f << v[ i ] << ' ';
    f.close( );
    return 0;
}