Cod sursa(job #3218938)

Utilizator tMario2111Neagu Mario tMario2111 Data 28 martie 2024 16:53:32
Problema Interclasari Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <iostream>
#include <fstream>

const int NMAX = 1e8;
int H[NMAX + 1];

int father(int nod)
{
    return nod / 2;
}

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

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

void HeapUp(int K)
{
    while (K > 1 && H[K] < H[father(K)])
    {
        std::swap(H[K], H[father(K)]);
        K = father(K);
    }
}

void HeapDown(int N, int K)
{
    while (true)
    {
        int son = 0;
        if (left_son(K) <= N)
        {
            son = left_son(K);
            if (right_son(K) <= N && H[right_son(K)] < H[son])
            {
                son = right_son(K);
            }
        }
        if (son && H[son] < H[K])
        {
            std::swap(H[son], H[K]);
            K = son;
        }
        else
        {
            break;
        }
    }
}

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

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

void extract_min(int &N)
{
    std::swap(H[1], H[N]);
    N--;
    HeapDown(N, 1);
}

void build(int N)
{
    for (int i = N / 2; i >= 1; i--)
    {
        HeapDown(N, i);
    }
}

void Delete(int &N, int K)
{
    std::swap(H[K], H[N]);
    N--;
    if ((K > 1) && (H[K] < H[father(K)]))
    {
        HeapUp(K);
    }
    else
    {
        HeapDown(N, K);
    }
}

void decrease_key(int K, int value)
{
    H[K] -= value;
    HeapUp(K);
}

void increase_key(int N, int K, int value)
{
    H[K] += value;
    HeapDown(N, K);
}

int main()
{
    std::ifstream f("interclasari.in");
    int nr_echipe;
    f >> nr_echipe;
    int heap_size = 0;
    for (int i = 0, nr_poze, j, poza; i < nr_echipe; ++i)
    {
        f >> nr_poze;
        for (j = 0; j < nr_poze; ++j)
        {
            f >> poza;
            insert(heap_size, poza);
        }
    }
    f.close();

    std::ofstream g("interclasari.out");
    g << heap_size << '\n';
    while (heap_size > 0)
    {
        g << H[1] << ' ';
        extract_min(heap_size);
    }
    g.close();
    return 0;
}