Cod sursa(job #1538349)

Utilizator ilinoiuflaviusIlinoiu Flavius ilinoiuflavius Data 28 noiembrie 2015 20:57:22
Problema Heapuri Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <iostream>
#include <fstream>
#define nmax 200001
using namespace std;

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

int n,v[nmax],cron[nmax],k;
void exch(int a,int b)
{
    int aux;
    aux=v[a];
    v[a]=v[b];
    v[b]=aux;
}
void exchc(int a,int b)
{
    int aux;
    aux=cron[a];
    cron[a]=cron[b];
    cron[b]=aux;
    /*cout<<"###\n";
    for(int i=1;i<=k;i++)cout<<cron[i]<<" ";cout<<endl;
    cout<<"###\n";*/
}
void down(int poz)
{
    int p=poz;
    while(poz*2 <= k)
    {
        if(poz*2+1 > k)
        {
            if(v[poz]>v[poz*2])exch(poz,poz*2),exchc(p,poz*2),poz=poz*2;
        }
        else
        {
            if(v[poz*2] < v[poz*2+1])
            {
                if(v[poz]>v[poz*2])exch(poz,poz*2),exchc(p,poz*2),poz=poz*2;
            }
            else if(v[poz]>v[poz*2+1])exch(poz,poz*2+1),exchc(p,poz*2+1),poz=poz*2+1;
        }
        poz=poz*2;
    }
}
void add()
{
    int x; f>>x;
    k++;
    v[k]=x;
    cron[k]=k;

    int z=k;
    while(z/2)
    {
        if(v[z] < v[z/2])
            exch(z,z/2),exchc(k,z/2);
        z=z/2;
    }
}

void substr()
{
    int x;
    f>>x;
    x=cron[x];
    exch(x,k);//,exchc(x,k);
    k--;
    down(x);
}

void min()
{
    f<<v[1]<<endl;
}
void read()
{
    int a,b;
    f>>n;
    for(int i=1;i<=n;i++)
    {
        f>>a;
        if(a==1)add();
        else if(a==2)substr();
        else min();
        /*cout<<"sir:  \n";
        for(int i=1;i<=k;i++)cout<<v[i]<<" ";cout<<endl;
        for(int i=1;i<=k;i++)cout<<cron[i]<<" ";cout<<endl;*/
    }

}

int main()
{
    read();
    return 0;
}