Cod sursa(job #1348151)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 19 februarie 2015 15:41:19
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <cstdio>
#include <array>
#include <vector>

using namespace std;

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

int N;
vector < int > V;
inline void radix( ) {
    array < vector < int >, ( 1 << 8 ) > b;
    for( register unsigned i = 0; i < 4; ++i ) {
        for( register int j = 0; j < N; ++j )
            b[ ( V[ j ] >> ( i << 3 ) ) & 0xFF ].push_back( V[ j ] );
        auto j = V.begin( );
        for( auto& bucket : b ) {
            for( auto buck : bucket )
                *( j++ ) = buck;
            bucket.clear( );
        }
    }
}
int main( ) {
    FILE *f;
    int A, B, C;

    f = fopen( IN_FILE, "r" );
    fscanf( f, "%d%d%d%d", &N, &A, &B, &C );
    fclose( f );
    V.push_back( B );
    for( int i = 1; i != N; ++i )
        V.push_back( ( static_cast < long long > ( A * V[ i - 1 ] ) % C + B ) % C );
    radix( );
    f = fopen( OUT_FILE, "w" );
    for( int i = 0; i != N; i += 10 )
        fprintf( f, "%d ", V[ i ] );
    fclose( f );
    return 0;
}