Cod sursa(job #3235370)

Utilizator Zen4415Stefan Zen4415 Data 17 iunie 2024 14:32:43
Problema Interclasari Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("interclasari.in");
ofstream fout("interclasari.out");

const int NMAX = 20e6;
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() {
    int n, currH = 0;
    fin >> n;
    for (int i = 0; i < n; i++){
        int k;
        fin >> k;
        for (int j = 0; j < k; j++){
            int value;
            fin >> value;
            H[++currH] = value;
        }
    }
    build(currH);
    fout << currH << '\n';
    while (currH){
        fout << find_min() << ' ';
        extract_min(currH);
    }
    return 0;
}