Pagini recente » Cod sursa (job #1616583) | Cod sursa (job #2773657) | Cod sursa (job #613315) | Cod sursa (job #2662390) | Cod sursa (job #1605312)
#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;
}