Cod sursa(job #1713758)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 6 iunie 2016 15:54:33
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<fstream>
#include<queue>

using namespace std;

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

const int nmax = 1e7;
const int radix = 256 - 1;
int n;
int v[ nmax + 1 ];

queue< int > q[ 2 ][ radix + 1 ];

void radix_sort() {
    int ind = 0;
    for( int i = 1; i <= n; ++ i ) {
        q[ ind ][ v[ i ] & radix ].push( v[ i ] );
    }

    ind = 1;
    for( int x = 8; x < 32; x += 8, ind = 1 - ind ) {
        for( int i = 0; i <= radix; ++ i ) {
            while ( !q[ 1 - ind ][ i ].empty() ) {
                int k = q[ 1 - ind ][ i ].front();
                q[ 1 - ind ][ i ].pop();
                q[ ind ][ (k >> x) & radix ].push( k );
            }
        }
    }
    ind = 1 - ind;
    n = 0;
    for( int i = 0; i <= radix; ++ i ) {
        while ( !q[ ind ][ i ].empty() ) {
            v[ ++ n ] = q[ ind ][ i ].front();
            q[ ind ][ i ].pop();
        }
    }
}
int main() {
    long long a, b, c;
    fin >> n >> a >> b >> c;

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

    radix_sort();

    for( int i = 1; i <= n; i += 10 ) {
        fout << v[ i ] << " ";
    }
    fout << "\n";

    fin.close();
    fout.close();
    return 0;
}