Cod sursa(job #1091716)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 25 ianuarie 2014 22:47:58
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const long long digits = 8;        //Digits
const long long r = 6;            //Bits
const long long radix = 1 << r;    //Buckets
const long long mask = radix - 1;  //BitMask

void RadixSort( vector<long long>& a )
{
    const long long SIZE = a.size();

    vector <long long> b( SIZE );
    vector <long long> bucket( radix );

    for ( long long i = 0, shift = 0; i < digits; ++i, shift += r )
    {
        for ( long long j = 0; j < radix; ++j )
                bucket[j] = 0;

        for ( long long j = 0; j < SIZE; ++j )
                ++bucket[ ( a[j] >> shift ) & mask ];

        for ( long long j = 1; j < radix; j++ )
                bucket[j] += bucket[j - 1];

        for ( long long j = SIZE - 1; j >= 0; --j )
                b[ --bucket[ ( a[j] >> shift ) & mask ] ] = a[j];

        for ( long long j = 0; j < SIZE; j++ )
                a[j] = b[j];
    }
}


void read( vector<long long>& a )
{
    ifstream f("radixsort.in");

    long long N, A, B, C;

    f >> N >> A >> B >> C;

    a.push_back( B );

    for ( long long i = 1; i < N; ++i )
    {
        long long x = ( 1LL * A * a[i - 1] + B ) % C;

        a.push_back( x );
    }

    f.close();
}

void write( vector<long long> a )
{
    ofstream g("radixsort.out");

    for ( long long i = 0; i < a.size(); i+=10 )
            g << a[i] << " ";

    g << "\n";

    g.close();
}

int main()
{
    vector<long long> v;

    read(v);
    RadixSort(v);
    write(v);

    return 0;
}