Cod sursa(job #3176571)

Utilizator vladimir.gavris.1Gavris Mihai Vladimir vladimir.gavris.1 Data 27 noiembrie 2023 12:48:31
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
#include <string.h>

#define BITSMAX 32
#define MAXN 10000000
#define BITS_PER_STEP 8
#define BASE ( 1 << BITS_PER_STEP )
#define MASK ( BASE - 1 )


using namespace std;

ifstream in( "radixsort.in" );
ofstream out( "radixsort.out" );

int aa[ MAXN ], bb[ MAXN ];
int frecv[ BASE + 1 ], ind[ BASE + 1];

void radix( int v[ ], int aux[ ], int n, int bits )
{
    if( bits == BITSMAX )
    {
        return;
    }

    memset( frecv, 0, sizeof( frecv ) );

    int i;
    for( i = 0; i < n; i++ )
    {
        frecv[ v[ i ] >> bits & MASK ]++;
    }

    ind[ 0 ] = 0;
    for( i = 1; i <= BASE; i++ )
    {
        ind[ i ] = ind[ i - 1 ] + frecv[ i - 1 ];
    }

    for( i = 0; i < n; i++ )
    {
        aux[ ind[ v[ i ] >> bits & MASK ]++ ] = v[ i ];
    }

    radix( aux, v, n, bits + BITS_PER_STEP );
}


int main()
{
    int i, n, a, b, c;
    in >> n >> a >> b >> c;

    aa[ 0 ] = b;
    for( i = 1; i < n; i++ )
    {
        aa[ i ] = ( ( long long ) a * aa[ i - 1 ] + b ) % c;
    }

    radix( aa, bb, n, 0 );

    for( i = 0; i < n; i += 10 )
    {
        out << aa[ i ] << ' ';
    }
    return 0;
}