Cod sursa(job #1841662)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 5 ianuarie 2017 21:16:38
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
# include <iostream>
# include <fstream>

# include <cstring>

using namespace std;

# define MAX_N 10000000
int v[MAX_N];

void radix_sort( int a[], int n )
{
    int * b = new int[n];
    int * v[2] = { a, b };

    for ( int b = 0; b < 32; b += 8 ) {
        int f[256], ix[256];

        memset( f, 0, sizeof ( f ) );

        for ( int i = 0; i < n; i ++ )
            f[( v[0][i] >> b ) & 255] ++;
        ix[0] = 0;
        for ( int i = 1; i < 256; i ++ )
            ix[i] = ix[i - 1] + f[i - 1];

        for ( int i = 0; i < n; i ++ )
            v[1][ix[( v[0][i] >> b ) & 255] ++] = v[0][i];

        swap( v[0], v[1] );
    }
}


int main()
{
    ifstream fin( "radixsort.in" );
    ofstream fout( "radixsort.out" );

    int n, a, b, c;
    fin >> n >> a >> b >> c;

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

    radix_sort( v, n );

    for ( int i = 0; i < n; i += 10 )
        fout << v[i] << ' ';

    fin.close();
    fout.close();

    return 0;
}