Pagini recente » Cod sursa (job #3190216) | Cod sursa (job #1593898) | Cod sursa (job #707509) | Cod sursa (job #221038) | Cod sursa (job #1200007)
#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;
}