Cod sursa(job #1200007)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 21 iunie 2014 15:17:58
Problema Interclasari Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include<fstream>
using namespace std;
ifstream fi("interclasari.in");
ofstream fo("interclasari.out");

template <class T>
void swap_T(T &x, T &y){
     T aux;
     aux=x;
     x=y;
     y=aux;
}

template <class T>
class min_heap{
      T a[20000007];
      int heap_size;
      void down_heap(int k);
      void up_heap(int k);
      public:
             min_heap():heap_size(0){}
             ~min_heap(){}
             
             int size()const{ return heap_size; }
             int minim()const{ return a[1]; }
             void inserare(T x);
             void stergere_minim();
};

template <class T>
void min_heap<T>::down_heap(int k){
     int son=1;
     
     while(son)
     {
      son=0;
      if(2*k<=heap_size){
                         son=2*k;
                         if(2*k+1<=heap_size && a[2*k+1]<a[2*k])
                           son=2*k+1;
                           
                         if(a[son]<a[k]){
                                         swap_T(a[son],a[k]);
                                         k=son; 
                                        }
                         else son=0;
                        }
     }
}

template <class T>
void min_heap<T>::up_heap(int k){
     while(k>1 && a[k]<a[k/2]){
                               swap_T(a[k],a[k/2]);
                               k=k/2;
                              }
}

template <class T>
void min_heap<T>::inserare(T x){
     heap_size++;
     a[heap_size]=x;
     
     up_heap(heap_size);
}

template <class T>
void min_heap<T>::stergere_minim(){
     a[1]=a[heap_size];
     heap_size--;
     
     down_heap(1);
}

int t,n,nr,x,i;
min_heap <int> h;

int main(){
    fi>>t;
    
    while(t){
             fi>>nr; 
             for(;nr>0;nr--){ fi>>x; h.inserare(x); }
             t--;
            }
    
    fo<<h.size()<<"\n";
    n=h.size();
    for(i=1;i<=n;i++){
                      fo<<h.minim()<<" ";
                      h.stergere_minim();
                     }
    
    fi.close();
    fo.close();
    return 0;
}