Cod sursa(job #1605312)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 18 februarie 2016 21:55:15
Problema Interclasari Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.12 kb
#include <cstdio>

using namespace std;

class input_reader {
    private:
        FILE *input_file;
        static const int SIZE = 1 << 17;
        char buffer[SIZE]; int cursor, sign;
        long long fractional_part;

        void advance() {
            if( ++cursor == SIZE ) {
                cursor = 0;
                fread( buffer, SIZE, 1, input_file );
            }
            return;
        }
    public:
        input_reader( const char *file_name, const char *file_type ) {
            input_file = fopen( file_name, file_type ); cursor = 0;
            fread( buffer, SIZE, 1, input_file );
        }

        template <class Type>
        input_reader &operator >>( Type &value ) {
            value = 0; sign = 1; fractional_part = 10;

            while( buffer[cursor] < '0' || buffer[cursor] > '9' ) {
                if( buffer[cursor] == '-' )
                    sign = 1;
                advance();
            }

            while( buffer[cursor] >= '0' && buffer[cursor] <= '9' ) {
                value = value * 10 + ( buffer[cursor] - '0' ) * sign;
                advance();
            }

            return *this;
        }

} input_file( "interclasari.in", "r" );

template <typename Type>
void nrx_swap( Type &value1, Type &value2 ) {
    Type value3 = value1; value1 = value2; value2 = value3;
    return;
}

template <class Type>
class min_heap {
    private:
        static const int SIZE = 1 << 22;
        Type my_heap[SIZE]; int heap_size;

        void up( int son ) {
            int father = son / 2;

            if( father && my_heap[father] > my_heap[son] ) {
                nrx_swap( my_heap[father], my_heap[son] );
                up( father );
            }

            return;
        }

        void down( int father ) {
            int son = father * 2;

            if( son + 1 <= heap_size && my_heap[son] > my_heap[son + 1] )
                son ++;

            if( son <= heap_size && my_heap[father] > my_heap[son] ) {
                nrx_swap( my_heap[father], my_heap[son] );
                down( son );
            }

            return;
        }
    public:
        void add_value( Type value ) {
            my_heap[++heap_size] = value;
            up( heap_size );
            return;
        }

        void delete_value( int position ) {
            nrx_swap( my_heap[position], my_heap[heap_size--] );
            down( position );
            return;
        }

        int get_size() {
            return heap_size;
        }

        Type get_min() {
            return my_heap[1];
        }
};

int K, X, N, S;
min_heap <int> my_heap;

int main () {

    freopen( "interclasari.out", "w", stdout );

    input_file >> K;
    for( int i = 1; i <= K; i ++ ) {
        input_file >> N; S += N;

        for( int j = 1; j <= N; j ++ ) {
            input_file >> X;
            my_heap.add_value( X );
        }
    }

    printf( "%d\n", S );
    while( my_heap.get_size() > 0 ) {
        printf( "%d ", my_heap.get_min() );
        my_heap.delete_value( 1 );
    }

    return 0;
}