Pagini recente » Cod sursa (job #2214000) | Cod sursa (job #3159090) | Cod sursa (job #497384) | Cod sursa (job #296102) | Cod sursa (job #3235260)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e8;
int H[NMAX + 1];
int father(int nod) {
return nod / 2;
}
int left_son(int nod) {
return nod * 2;
}
int right_son(int nod) {
return nod * 2 + 1;
}
void HeapUp(int K) {
while(K > 1 && H[K] < H[father(K)]) {
swap(H[K], H[father(K)]);
K = father(K);
}
}
void HeapDown(int N, int K) {
while(true) {
int son = 0;
if(left_son(K) <= N) {
son = left_son(K);
if(right_son(K) <= N && H[right_son(K)] < H[son]) {
son = right_son(K);
}
}
if(son && H[son] < H[K]) {
swap(H[son], H[K]);
K = son;
} else {
break;
}
}
}
void insert(int &N, int value) {
H[++N] = value;
HeapUp(N);
}
int find_min() {
return H[1];
}
void extract_min(int &N) {
swap(H[1], H[N]);
N--;
HeapDown(N, 1);
}
void build(int N) {
for (int i = N / 2; i >= 1; i--) {
HeapDown(N, i);
}
}
void Delete(int& N, int K) {
swap(H[K], H[N]);
N--;
if ((K > 1) && (H[K] < H[father(K)])) {
HeapUp(K);
} else {
HeapDown(N, K);
}
}
void decrease_key(int K, int value) {
H[K] -= value;
HeapUp(K);
}
void increase_key(int N, int K, int value) {
H[K] += value;
HeapDown(N, K);
}
int main() {
//heapsort
// ifstream in ("heap_sort.in");
// ofstream out ("heap_sort.out");
// int n, x, size = 0;
// in >> n;
// for(int i = 0; i < n; i++) {
// in >> x;
// insert(size, x);
// }
// while(size) {
// out << find_min() << " ";
// extract_min(size);
// }
//last k
// int n, k, A, B, C, D;
// cin >> n >> k >> A >> B >> C >> D;
// int size = 0;
// int anterior = A;
// insert(size, A);
// for (int i = 1; i < n; i++){
// int aux = (B * anterior + C) % D;
// if (size < k){
// insert(size, aux);
// }
// else if (aux > find_min()){
// Delete(size, 1);
// insert(size, aux);
// }
// anterior = aux;
// }
// for (int i = 0; i < k; i++){
// cout << find_min() << " ";
// extract_min(size);
// }
ifstream in("interclasari.in");
ofstream out("interclasari.out");
int k, n, x, size = 0;
in >> k;
for(int i = 0; i < k; i++) {
in >> n;
for(int j = 0; j < n; j++) {
in >> x;
insert(size, x);
}
}
n = size;
out << n << endl;
for (int i = 0; i < n; i++){
out << find_min() << " ";
extract_min(size);
}
return 0;
}