Cod sursa(job #2964527)

Utilizator TanasaStefanTanasa Stefan TanasaStefan Data 13 ianuarie 2023 09:50:43
Problema Heapuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("heapuri.in");
ofstream g("heapuri.out");

int h[1000005] , n;

inline int father(int nod)
{
    return nod / 2;
}

inline left_son(int nod)
{
    return 2 * nod;
}

inline right_son(int nod)
{
    return nod * 2 + 1;
}

void sift( int n , int k)
{
    int son;
    do
    {
        son = 0;

        if(left_son(k) <= n)
        {
            son = left_son(k);
            if(right_son(k) <= n && h[right_son(k)] > h[left_son(k)])
                son = right_son(k);
        if(h[son] <= h[k])
            son = 0;
        }
        if(son)
        {
            swap(h[k] , h[son]);
            k = son;
        }

    }while(son);
}

void percolate(int n , int k)
{
    int key = h[k];

    while((k > 1) && (key > h[father(k)]))
    {
        h[k] = h[father(k)];
        k = father(k);
    }

    h[k] = key;
}

void insert(int &n , int key)
{
    h[++n] = key;
    percolate(n , n);
}
void cut(int &n , int k)
{
    h[k] = h[n];
    --n;

    if((k > 1)  && (h[k] > h[father(k)]))
        percolate(n , k);
    else
        sift(
             n ,k);
}
int main()
{
    f >> n;
    for ( int i = 1 ; i <= n ;i++)
    {
        int x = 0 , y = 0;
        f >> x >> y;
    }
    return 0;
}