Cod sursa(job #1790938)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 28 octombrie 2016 21:30:31
Problema Interclasari Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MaxN 20000001
#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=N/2;i>0;i--)
		Down_Heap(i);
}
int main()
{
    IN=fopen("intercalsari.in","r");
    OUT=fopen("intercalsari.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;
}