Cod sursa(job #1789424)

Utilizator ionutpop118Pop Ioan Cristian ionutpop118 Data 26 octombrie 2016 23:36:36
Problema Interclasari Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int NMAX = 500000;

int n, k, p;
int heap[NMAX + 5];

void hinsert(int x)
{
    heap[++k] = x; p = k;
    while (p > 1 && heap[p] < heap[p >> 1])
    {
        swap(heap[p], heap[p >> 1]);
        p >>= 1;
    }
}

void heapsort()
{
    for (int i = 1; i <= n; ++i)
    {
        printf("%d ", heap[1]);
        heap[1] = heap[k];
        --k; p = 1;

        while ((p << 1) <= k)
        {
            int st = (p << 1);
            int dr = st + 1;
            int best = st;

            if (dr <= k && heap[st] > heap[dr])
                best = dr;
            if (heap[p] > heap[best])
                swap(heap[p], heap[best]);
            else
                break;
            p = best;
        }
    }
}

int main()
{
    freopen("interclasari.in", "r", stdin);
    freopen("interclasari.out", "w", stdout);

    int m; scanf("%d", &m);
    for (int i = 1; i <= m; ++i)
    {
        int ni; scanf("%d", &ni); n += ni;
        for (int i = 1; i <= ni; ++i)
        {
            int x;
            scanf("%d", &x);
            hinsert(x);
        }
    }
    printf("%d\n", n);
    heapsort();
    return 0;
}