Cod sursa(job #1841660)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 5 ianuarie 2017 21:15:18
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 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 += 11 ) {
        int f[2048], ix[2048];

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

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

        for ( int i = 0; i < n; i ++ )
            v[1][ix[( v[0][i] >> b ) & 2047] ++] = 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;
}