Cod sursa(job #3235260)

Utilizator Programator060804Ungureanu Vlad Constantin Programator060804 Data 16 iunie 2024 17:17:56
Problema Interclasari Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.64 kb
#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;
}