Cod sursa(job #3175779)

Utilizator vladimir.gavris.1Gavris Mihai Vladimir vladimir.gavris.1 Data 26 noiembrie 2023 13:29:53
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <vector>

using namespace std;

#define MAXN 10000000
#define BITS_STEP 4
#define BITSMAX 32
#define BAZA 1 << BITS_STEP
const int MASK = 15;

int n, a, b, c, contor = 1;

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

int v[ MAXN + 1 ];
vector<int> galeti[ BAZA ];

void ggenerate()
{
		int i;
		v[ 0 ] = b;
		for( i = 1; i < n; i++ )
		{
				v[ i ] = ( a * v[ i - 1 ] + b ) % c;
		}
}

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

		int i, j;
		unsigned int k;

		for( i = 0; i < n; i++ )
		{
				galeti[ v[ i ] >> bits & MASK ].push_back( v[ i ] );
		}

		i = 0;
		for( j = 0; j < BAZA; j++ )
		{
				for( k = 0; k < galeti[ j ].size(); k++ )
				{
						v[ i ]= galeti[ j ][ k ];
						i++;
				}
				galeti[ b ].clear();
		}

		radixsort( v, n, bits + BITS_STEP );
}

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

		ggenerate();
    radixsort( v, n, 0 );

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

38 23  110 5 98 107 92 35 89 122 26 104 56 95 71 29 17 119 113 41 38 2 62 44 74 65 80 14 83 50 23 68 116 77 101 20 32 53 59 8 11 47 110 5 98 107 92 35 89 122 26 104 56 95 71 29 17 119 113 41 38 2 62 44 74 65 80 14 83 50 23 68 116 77 101 20 32 53 59