Cod sursa(job #1185067)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 14 mai 2014 22:17:49
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int Nmax = 10000000;
const int DIGITS = 4;
const int R = 32 / DIGITS;
const int radix = ( 1 << R );
const int mask = radix - 1;

int A[Nmax], B[Nmax], buckets[radix];
int N, a, b, c;

void RadixSort()
{
    for ( int d = 0, shift = 0; d < DIGITS; ++d, shift += R )
    {
        for ( int i = 0; i < radix; ++i )
                buckets[i] = 0;

        for ( int i = 0; i < N; ++i )
                ++buckets[ ( A[i] >> shift ) & mask ];

        for ( int i = 1; i < radix; ++i )
                buckets[i] += buckets[i - 1];

        for ( int i = N - 1; i >= 0; i-- )
                B[ --buckets[ ( A[i] >> shift ) & mask ] ] = A[i];

        for ( int i = 0; i < N; ++i )
                A[i] = B[i];
    }
}

int main()
{
    ifstream f("radixsort.in");
    ofstream g("radixsort.out");

    f >> N >> a >> b >> c;

    A[0] = b;

    for ( int i = 1; i < N; ++i )
            A[i] = ( 1LL * a * A[i - 1] + b ) % c;

    RadixSort();

    for ( int i = 0; i < N; i += 10 )
            g << A[i] << " ";

    return 0;
}