Cod sursa(job #1841647)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 5 ianuarie 2017 20:52:25
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
# include <iostream>
# include <fstream>

# include <vector>

using namespace std;

# define MAX_N 10000000
int v[MAX_N];

# define MASK 255
vector<int> bucket[1 + MASK];

void radix_sort( int v[], int n )
{
    for ( int b = 0; b < 32; b += 8 ) {
        for ( int i = 0; i < n; i ++ ) {
            int k = ( v[i] >> b & MASK );
            bucket[k].push_back( v[i] );
        }

        int p = 0;
        for ( int i = 0; i < MASK; i ++ ) {
            for ( int j : bucket[i] )
                v[p ++] = j;

            bucket[i].clear();
        }
    }
}


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;
}