Cod sursa(job #3295898)

Utilizator _irina__irina tanase _irina__ Data 9 mai 2025 16:15:11
Problema Interclasari Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <bits/stdc++.h>
#include <fstream>

using namespace std;

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

int heap[1000001], sz;

void up(int);

int parent(int pos)
{
    return pos / 2;
}

int left_son(int pos)
{
    return pos * 2;
}

int right_son(int pos)
{
    return pos * 2 + 1;
}

void push(int val)
{
    sz ++;
    heap[sz] = val;
    up(sz);
}

void up(int pos)
{
    while(pos > 1 && heap[pos] < heap[parent(pos)])
    {
        swap(heap[pos], heap[parent(pos)]);
        pos = parent(pos);
    }
}

void down(int pos)
{
    while(1)
    {
        if(left_son(pos) > sz)
            break;

        int next_pos = left_son(pos);

        if((heap[right_son(pos)] < heap[next_pos]) && (right_son(pos) <= sz))
            next_pos = right_son(pos);

        if(heap[pos] < heap[next_pos])
            break;
        else
        {
            swap(heap[pos], heap[next_pos]);
            pos = next_pos;
        }
    }
}

int minim()
{
    return heap[1];
}

int pop()
{
    int a = heap[1];

    swap(heap[1], heap[sz]);
    sz --;
    down(1);

    return a;
}

int main()
{
    int n, k, x;

    fin >> k;

    for(int i = 1; i <= k; i ++)
    {
        fin >> n;
        for(int j = 1; j <= n; j ++)
        {
            fin >> x;
            push(x);
        }
    }

    int s = sz;

    fout << s << endl;

    for(int i = 1; i <= s; i ++)
    {
        fout << pop() << ' ';
    }
}