Cod sursa(job #1795904)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 2 noiembrie 2016 22:22:43
Problema Interclasari Scor 100
Compilator cpp Status done
Runda cerculdeinfo-lectia5-paduri.heap.aib Marime 1.21 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MaxN 20000005
#define INF 2140000000
 
using namespace std;
 
FILE *IN,*OUT;
int T,N,P=0,v[MaxN],HeapSize;
inline void Down_Heap(int pos)
{
    int Min,Minpos,aux;
    while(2*pos<=HeapSize)
    {
        Min=v[2*pos],Minpos=2*pos;
        if(2*pos+1<=HeapSize&&Min>v[2*pos+1])
            Min=v[2*pos+1],Minpos=2*pos+1;
        if(v[pos]>Min)
        {
            aux=v[Minpos];
            v[Minpos]=v[pos];
            v[pos]=aux;
            pos=Minpos;
        }
        else return;
    }
}
inline void Delete_Min()
{
    int aux=v[1];
    v[1]=v[HeapSize];
    v[HeapSize--]=aux;
    Down_Heap(1);
}
inline void Heapify()
{
    for(int i=HeapSize/2;i>0;i--)
        Down_Heap(i);
}
int main()
{
    IN=fopen("interclasari.in","r");
    OUT=fopen("interclasari.out","w");
 
    fscanf(IN,"%d",&T);
    for(int t=1;t<=T;t++)
    {
        fscanf(IN,"%d",&N);
        for(int i=1;i<=N;i++)
            fscanf(IN,"%d",&v[++P]);
    }
    HeapSize=P;
    Heapify();
    fprintf(OUT,"%d\n",P);
    for(int i=1;i<=P;i++)
    {
        fprintf(OUT,"%d ",v[1]);
        Delete_Min();
    }
    return 0;
}