Cod sursa(job #2767452)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 6 august 2021 11:39:10
Problema Interclasari Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#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;
}