Cod sursa(job #1789518)

Utilizator antanaAntonia Boca antana Data 27 octombrie 2016 08:25:53
Problema Interclasari Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <cstdio>
#include <cctype>
#define MAXK 20
#define MAXN 1000000
#define BUF_SIZE (1<<17)

int n, pos = BUF_SIZE, heap[1+MAXN*MAXK];
char buf[BUF_SIZE];

FILE *fin, *fout;

inline char getChar();
inline int getInt();
inline int father(int x){ return x/2;}
inline int son_left(int x){return x*2;}
inline int son_right(int x){ return x*2+1;}
inline void swap1(int x, int y){
    int aux;
    aux = heap[x];
    heap[x] = heap[y];
    heap[y] = aux;
}

inline void down(int x)
{
    int p, q, f = 1;

    while(son_left(x) <= n && f)
    {
        f = 0;
        p = son_left(x);
        q = son_right(x);
        if(q <= n && heap[q] < heap[p])
            p = q;
        if(heap[p] < heap[x])
            swap1(p, x), f = 1;
        x = p;
    }
}

inline void heapify()
{
    int i;
    for(i=n/2; i>=1; --i)
        down(i);
}

int main()
{
    fin = fopen("interclasari.in", "r");
    fout = fopen("interclasari.out", "w");

    int i, j, k, p;

    k = getInt();
    for(i=1; i<=k; ++i)
    {
        p = getInt();
        for(j=1; j<=p; ++j)
            heap[++n] = getInt();
    }

    heapify();

    fprintf(fout, "%d\n", n);
    while(n)
    {
        fprintf(fout, "%d ", heap[1]);
        swap1(1, n);
        n--;
        down(1);
    }

    return 0;
}

inline char getChar(){
    if(pos == BUF_SIZE) pos = 0, fread(buf, 1, BUF_SIZE, fin);
    return buf[pos++];
}

inline int getInt(){
    int nr = 0;
    char c;

    c = getChar();
    while(!isdigit(c)) c = getChar();
    while(isdigit(c))
    {
        nr = nr*10 + c -'0';
        c = getChar();
    }

    return nr;
}