Pagini recente » Cod sursa (job #668553) | Cod sursa (job #41433) | Cod sursa (job #1929717) | Cod sursa (job #2317950) | Cod sursa (job #2767452)
#include <bits/stdc++.h>
using namespace std;
bool smaller(int a,int b) {
return a < b;
}
template <typename T>
class heap {
private:
vector<int> t;
int parrent(int idx) {
return idx/2;
}
bool (*comp)(T a, T b);
int left_son(int idx) {
return 2 * idx;
}
int right_son(int idx) {
return 2 * idx + 1;
}
void upHeap(int idx) {
while(idx > 1 && comp(t[idx], t[parrent(idx)]) ) {
swap(t[parrent(idx)], t[idx]);
idx = parrent(idx);
}
}
void downHeap(int idx) {
// recursiv
int best = idx;
if(left_son(idx) <= size() && comp(t[left_son(idx)], t[best]) ) {
best = left_son(idx);
}
if(right_son(idx) <= size() && comp(t[right_son(idx)],t[best] )) {
best = right_son(idx);
}
if(best != idx) {
swap(t[best], t[idx]);
downHeap(best);
}
}
public:
int size() {
return t.size() - 1;
}
heap(bool (* f)(T a, T b) ) {
t.resize(1);
comp = f;
}
void insert(T val) {
t.push_back(val);
upHeap(size());
}
void pop() {
swap(t[1], t[size()]);
t.pop_back();
downHeap(1);
}
T top() {
return t[1];
}
};
int main() {
freopen("interclasari.in","r",stdin);
freopen("interclasari.out","w",stdout);
int t;
scanf("%d",&t);
heap<int> h(smaller);
int total = 0;
while(t--) {
int n;
scanf("%d",&n);
total += n;
for(int i = 1; i <= n; i++) {
int x;
scanf("%d",&x);
h.insert(x);
}
}
//heap sort
printf("%d\n",total);
while(h.size()) {
printf("%d ",h.top());
h.pop();
}
printf("\n");
return 0;
}