Cod sursa(job #1512461)

Utilizator superstar1998Moldoveanu Vlad superstar1998 Data 28 octombrie 2015 08:49:35
Problema Heapuri Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <fstream>
using namespace std;
int H[200001],A[200001],Pos[200001],m,n,na;
void inserare(int x)
{
    A[++na]=x;
    H[++n]=x;
    int fiu,tata;
    fiu = n;
    tata = n/2;
    while(tata && H[tata]>x)
    {
        swap(Pos[H[tata]],Pos[H[fiu]]);
        H[fiu]=H[tata];
        fiu=tata;
        tata=fiu/2;
    }
    H[fiu]=x;
    Pos[fiu]=fiu;
}
void sterge(int x)
{
    H[Pos[A[x]]]=H[n];
    Pos[H[n]]=Pos[A[x]];
    n--;
    int fiu,tata,y;
    y=H[n+1];
    tata=Pos[A[x]];
    fiu=tata/2;
    while(fiu<=n)
    {
        if (fiu<n && H[fiu]>H[fiu+1]) fiu++;
        if (y>H[fiu])
        {
            Pos[H[tata]]=Pos[H[fiu]];
            H[tata]=H[fiu];
            tata = fiu;
            fiu=fiu*2;
        }
        else fiu=n+1;
    }
    Pos[y]=tata;
    H[tata]=y;
}
void afisare()
{
    for(int i=1;i<=n;i++)
        cout<<H[i]<<" ";
    cout<<endl;
    for(int i=1;i<=na;i++)
        cout<<A[i]<<" ";
    cout<<endl;
    for(int i=1;i<=na;i++)
        cout<<Pos[i]<<" ";
    cout<<endl;
}
int main()
{
    ifstream f("heapuri.in");
    ofstream g("heapuri.out");
    f>>m;
    int x,y;
    for(int i=1;i<=m;i++)
    {
        f>>x;
        if(x==1)
        {
            f>>y;
            inserare(y);
        }
        else if(x==2)
        {
            f>>y;
            sterge(y);
        }
        else g<<H[1]<<'\n';
        if(x<3)cout<<x<<" : ",afisare();

    }
    f.close();
    g.close();
    return 0;
}