Cod sursa(job #2223075)

Utilizator Nazarick24Andrei Ionescu Nazarick24 Data 19 iulie 2018 02:08:16
Problema Heapuri Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.42 kb
#include <algorithm>
#include <stdio.h>
int contor=1;

struct elem
{
    int nr;
    int ordine=0;
};
elem v[1000];
void heap(elem v[],int p)
{
    elem aux;


    while(p!=1 && v[p].nr<v[p/2].nr)
    {


        aux=v[p];
        v[p]=v[p/2];
        v[p/2]=aux;

        p=p/2;

    }

}
inline void eliminatorul (elem v[],int p)
{
    elem aux;
    v[p]=v[contor-1];
    contor--;
    bool unbalanced = true;
    while(unbalanced) ///cat timp heap-ul este nebalansat (e ceva in neregula cu el)
    {
        unbalanced = false;
        if((2*p+1)<contor)
        {
            if (v[p].nr > v[2*p].nr || v[p].nr > v[2*p+1].nr)  ///heap is unbalanced
            {
                unbalanced = true;
                if(v[2*p].nr < v[(2*p)+1].nr)
                {

                    aux=v[p];
                    v[p]=v[2*p];
                    v[2*p]=aux;

                    p=2*p;

                }
                else
                {
                    aux=v[p];
                    v[p]=v[2*p+1];
                    v[2*p+1]=aux;


                    p=(2*p)+1;
                }
            }

        }
        else
        {
            if(2*p<contor)
            {
                if (v[p].nr > v[2*p].nr) {
                    unbalanced = true;
                    aux=v[p];
                    v[p]=v[2*p];
                    v[2*p]=aux;
                    p=2*p;

                }
            }

        }
    }
}

int main()
{
    freopen("heapuri.in","r",stdin);
    freopen("heapuri.out","w",stdout);


    int i,n;

    scanf("%d",&n);
    int cod,x,num=1;
    for(i=0; i<n; i++)
    {
        scanf("%d",&cod);
        if(cod!=3)
        {
            scanf("%d",&x);
            if(cod==1)
            {
                v[contor].nr=x;
                v[contor].ordine=num;
                heap(v,contor);
                contor++;
                num++;

            }
            if(cod==2)
            {
                int q=1;
                int j=1;
                while(j<=contor && q!=0)
                {
                    if(x==v[j].ordine)
                    {
                        q=0;

                        eliminatorul(v,j);

                    }
                    j++;
                }
            }

        }
        else
            printf("%d\n", v[1].nr);
    }







}