Cod sursa(job #1424783)

Utilizator GinguIonutGinguIonut GinguIonut Data 25 aprilie 2015 15:23:41
Problema Interclasari Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <stdio.h>
#include <fstream>
#define dim 20000001
using namespace std;
int heap[dim],i,j,k,f,n,m,ans,val;
void upDate(int pozi)
{
    while(pozi/2>0)
    {
        if(heap[pozi]<heap[pozi/2])
        {
            swap(heap[pozi],heap[pozi/2]);
            pozi/=2;
        }
        else
            break;
    }
}
void downDate(int pozi)
{
    int po;
    while(pozi*2<=k)
    {
        po=pozi*2;
        if(po+1<=k&&heap[po]>heap[po+1])
            po++;
        if(heap[pozi]>heap[po])
        {
            swap(heap[pozi],heap[po]);
            pozi=po;
        }
        else
            break;
    }
}
int main()
{
    freopen("interclasari.in","r",stdin);
    freopen("interclasari.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&m);
        ans+=m;
        for(j=1;j<=m;j++)
        {
            scanf("%d",&val);
            heap[++k]=val;
            upDate(k);
        }
    }
    printf("%d\n",ans);
    for(i=1;i<ans;i++)
    {
        printf("%d ",heap[1]);
        heap[1]=heap[k];
        k--;
        downDate(1);
    }
    printf("%d",heap[1]);
    return 0;
}