Cod sursa(job #1458302)

Utilizator petru.cehanCehan Petru petru.cehan Data 7 iulie 2015 12:26:09
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <iostream>

using namespace std;

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

const int NMAX = 10000005;
const int MASK = (1 << 8) - 1; // 255

int n, A, B, C, key;
int v [NMAX], aux [NMAX], bucket [MASK + 2];

void Citire()
{
    fin >> n >> A >> B >> C;
    v[1] = B;
    int i ;
    for ( i = 2 ; i <= n ; ++ i )
    {
        v [i] = ( 1LL * A * v [i-1] + B ) % C ; // 1LL = conversie in long long
    }
}

void Radix_Sort()
{
    for ( int shift = 0 ; shift < 32 ; shift += 8 ) // 4pasi
    {
        for ( int i = 1 ; i <= n ; ++ i )
        {
            key = ( v[i] >> shift ) & MASK ; // mascare binară
            ++ bucket [ key ] ;
        }

        for ( int i = 0 ; i <= MASK ; ++ i )
        {
            bucket [i] += bucket [i - 1] ;
        }

        for ( int i = n ; i ; -- i )
        {
            key = ( v[i] >> shift ) & MASK; // mascare binară
            aux [bucket[key]--] = v[i];
        }

        for ( int i = 1 ; i <= n ; ++ i)
        {
            v [i] = aux [i];
        }

        for ( int i = 1 ; i <= MASK ; ++ i )
        {
            bucket[i] = 0;
        }
    }
}

void Afisare()
{
    for ( int i = 1 ; i <= n ; i += 10 )
        fout << v[i] << ' ';
}

int main()
{
    Citire ();
    Radix_Sort ();
    Afisare ();

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