Cod sursa(job #1495199)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 2 octombrie 2015 18:46:34
Problema Interclasari Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <bits/stdc++.h>

using namespace std;

const int Nmax = (int) 1e6;
const int Kmax = 20;
const int Mask = 255;
const int THRESHOLD = 100;

int v[Kmax * Nmax];

void insertionSort(int lo, int hi)
{
    for ( int i = lo + 1; i < hi; i++ )
    {
        int x = v[i];
        int j = i;
        while ( j > lo && x < v[j - 1] )
        {
            v[j] = v[j - 1];
            j--;
        }
        v[j] = x;
    }
}

void radixPass(int lo, int hi, int bits)
{
    int start[Mask + 1], finish[Mask + 1];

    memset ( finish, 0, sizeof( finish ) );

    for ( int i = lo; i < hi; i++ )
        finish[ (v[i] >> bits) & Mask ]++;

    start[0] = lo;
    finish[0] += lo;
    for ( int i = 1; i <= Mask; i++ )
    {
        start[i] = finish[i - 1];
        finish[i] += finish[i - 1];
    }

    for ( int i = 0; i <= Mask; i++ )
    {
        while ( start[i] != finish[i] )
        {
            int elem = v[start[i]];
            int bucket = ( elem >> bits ) & Mask;
            while ( bucket != i )
            {
                int tmp = v[ start[bucket] ];
                v[ start[bucket]++ ] = elem;
                elem = tmp;
                bucket = ( elem >> bits ) & Mask;
            }
            v[ start[i]++ ] = elem;
        }
    }
    if ( bits )
    {
        for ( int i = 0; i <= Mask; i++ )
        {
            int siz = finish[i] - ( i ? finish[i - 1] : lo );
            if ( siz > THRESHOLD )
                radixPass( finish[i] - siz, finish[i], bits - 8 );
            else if ( siz > 1 )
                insertionSort( finish[i] - siz, finish[i] );
        }
    }
}

int main()
{
    ifstream in("interclasari.in");
    ofstream out("interclasari.out");
    int k;
    int n, sum = 0;

    in >> k;
    for ( int i = 0; i < k; i++ )
    {
        in >> n;
        for ( int j = 0; j < n; j++ )
            in >> v[sum + j];
        sum += n;
    }
    in.close();

    radixPass(0, sum, 24);

    out << sum << '\n';
    for ( int i = 0; i < sum; i++ )
        out << v[i] << ' ';
    out.close();
    return 0;
}