Pagini recente » Cod sursa (job #1722723) | Cod sursa (job #728384) | Cod sursa (job #956457) | Cod sursa (job #1634113) | Cod sursa (job #1795682)
#include<cstdio>
#include<algorithm>
const int NMAX=20000007;
int heap[NMAX];
int marime_heap;
int Tata(int x)
{
return x/2;
}
int Fiu_st(int x)
{
return 2*x;
}
int Fiu_dr(int x)
{
return 2*x+1;
}
void Swap(int x,int y)
{
std::swap(heap[x],heap[y]);
}
void Down(int poz)
{
while(poz<marime_heap)
{
int best=poz;
if(Fiu_st(poz)<=marime_heap && heap[Fiu_st(poz)]<heap[best])
best=Fiu_st(poz);
if(Fiu_dr(poz)<=marime_heap && heap[Fiu_dr(poz)]<heap[best])
best=Fiu_dr(poz);
if(best==poz)
return;
Swap(best,poz);
poz=best;
}
}
void Up(int poz)
{
while(poz>1 && heap[Tata(poz)]<heap[poz])
{
Swap(poz,Tata(poz));
poz=Tata(poz);
}
}
void Remove_min()
{
Swap(1,marime_heap);
marime_heap--;
Down(1);
}
void Heapify()
{
for(int i=marime_heap/2;i>=1;i--)
Down(i);
}
int main()
{
FILE *in=fopen("interclasari.in","r");
int k;
fscanf(in,"%d ",&k);
for(int sq=1;sq<=k;sq++)
{
int n;
fscanf(in,"%d ",&n);
for(int i=1;i<=n;i++)
fscanf(in,"%d ",&heap[++marime_heap]);
}
fclose(in);
FILE *out=fopen("interclasari.out","w");
Heapify();
fprintf(out,"%d\n",marime_heap);
while(marime_heap>=1)
{
fprintf(out,"%d ",heap[1]);
Remove_min();
}
fclose(out);
return 0;
}