Cod sursa(job #1795682)

Utilizator nnnmmmcioltan alex nnnmmm Data 2 noiembrie 2016 19:46:29
Problema Interclasari Scor 90
Compilator cpp Status done
Runda cerculdeinfo-lectia5-paduri.heap.aib Marime 1.43 kb
#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;
}