Cod sursa(job #3235314)

Utilizator Cochior_Iuliacochior iulia-stefana Cochior_Iulia Data 17 iunie 2024 00:20:54
Problema Interclasari Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream f("interclasari.in");
ofstream g("interclasari.out");

const int NMAX = 1e5;
int H[NMAX], loc, echipe, n, x;

int parinte(int k)
{
    return k/2;
}

int stanga(int k)
{
    return 2*k;
}

int dreapta(int k)
{
    return 2*k+1;
}

void HeapUp(int k)
{
    while(k > 1 && H[k] < H[parinte(k)])
    {
        swap(H[k], H[parinte(k)]);
        k = parinte(k);
    }
}

void HeapDown(int& loc, int k)
{
    int fiu = 0;
    while(true)
    {
        if(stanga(k) <= loc)
        {
            fiu = stanga(k);
            if(dreapta(k) <= loc && H[dreapta(k)] < H[fiu])
                fiu = dreapta(k);
        }
        if(fiu && H[fiu] < H[k])
        {
            swap(H[fiu], H[k]);
            k = fiu;
        }
        else
            break;
    }
}

void insert(int& loc, int val)
{
    H[++loc] = val;
    HeapUp(loc);
}

void pop(int& loc)
{
    swap(H[1], H[loc]);
    loc--;
    HeapDown(loc, 1);
}

int top()
{
    return H[1];
}

bool goala(int loc)
{
    return !loc;
}

int main()
{
    f>>echipe;
    for(; echipe; echipe--)
    {
        f>>n;
        for(; n; n--)
        {
            f>>x;
            insert(loc, x);
        }
    }
    g<<loc<<'\n';
    while(!goala(loc))
    {
        g<<top()<<" ";
        pop(loc);
    }
    return 0;
}