Cod sursa(job #1361983)

Utilizator zpaePopescu Andreea zpae Data 26 februarie 2015 08:49:07
Problema Heapuri Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <algorithm>
using namespace std;
#define N 100000
int h[N],p[N],rp[N],n=0;

void heap_up(int k)
{
    while(k/2>=1&&h[k/2]>h[k])
    {
        swap(h[k],h[k/2]);
        swap(p[rp[k]],p[rp[k/2]]);
        swap(rp[k],rp[k/2]);
        k=k/2;
    }
}

int main()
{
    freopen("heapuri.in","r",stdin);
    freopen("heapuri.out","w",stdout);
    int m,s,x,i;
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d",&s);
        if(s==1)
        {
            scanf("%d",&x);
            n++;
            h[n]=x;
            p[n]=n;
            rp[n]=n;
            heap_up(n);

            for(i=0;i<=n;i++)
                printf("%d ",h[i]);
            printf("\n");
            for(i=0;i<=n;i++)
                printf("%d ",p[i]);
            printf("\n");
            for(i=0;i<=n;i++)
                printf("%d ",rp[i]);
            printf("\n");
            printf("\n");

        }
        else if(s==2)
        {
            scanf("%d",&x);
            swap(h[x],h[n]);
            swap(p[rp[x]],p[rp[n]]);
            swap(rp[x],rp[n]);
            n--;
        }
        else
            printf("%d\n",h[1]);
    }
    return 0;
}