Cod sursa(job #2417844)

Utilizator mihai2003LLL LLL mihai2003 Data 1 mai 2019 20:52:38
Problema Heapuri Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.89 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

struct node{
    node *st,*dr;
    int val;
}*bst;

node * find(int val,node * nod){
    if(nod==NULL)
        return NULL;
    if(nod->val==val)
        return nod;
    if(val>nod->val)
        return find(val,nod->dr);
    return find(val,nod->st);
}
node* newNode(int data)
{
    node* temp = new node;

    temp->val = data;

    temp->st = NULL;
    temp->dr = NULL;

    return temp;
}
node* insert(node* root, int val)
{
    node* newnode = newNode(val);
    node* x = root;
    node* y = NULL;
    while (x != NULL) {
        y = x;
        if (val < x->val)
            x = x->st;
        else
            x = x->dr;
    }

    if (y == NULL)
        y = newnode;
    else if (val < y->val)
        y->st = newnode;
    else
        y->dr = newnode;
    return y;
}

node * minb(node *start){
    while(start->st!=NULL)
        start=start->st;
    return start;
}

node * erase(int val,node *&nod){
    if(nod==NULL)
        return nod;
    if(val<nod->val)
        nod->st=erase(val,nod->st);
    else
        if(val>nod->val)
            nod->dr=erase(val,nod->dr);
        else{
            if(nod->st==NULL){
                node * tmp=nod->dr;
                delete nod;
                return tmp;
            }
            if(nod->dr==NULL){
                node * tmp=nod->st;
                delete nod;
                return tmp;
            }
            node *tmp=minb(nod->dr);
            nod->val=tmp->val;
            nod->dr=erase(tmp->val,nod->dr);
        }
    return nod;
}
class input_parser{
protected:
    FILE *fin;///Input file
    static const int max_load=1<<10;///Maximum Allocation
    size_t pos;///Index of the buffer
    char buffer[max_load];///Input is being store here
public:
    input_parser():pos(0){}
    input_parser(const char *);///Opens the specified file
    void open(const char *);///^
    template<class T>
    void read(T &);///Read function
    void read(){}
    template<class T,typename ... Args>
    void read(T & ,Args&...args);
    void read(char *,size_t);///Read a string
    inline char next();///Advances the buffer
};

input_parser::input_parser(const char * fName){
    this->fin=fopen(fName,"r");
    this->pos=0;
}

void input_parser::open(const char *fName){
    delete this->fin;
    memset(this->buffer,0,sizeof(this->buffer));
    this->fin=fopen(fName,"r");
    this->pos=0;
}

inline char input_parser::next(){
    if(this->pos==max_load)
            fread(this->buffer,1,max_load,this->fin),this->pos=0;
    return this->buffer[this->pos++];
}

template<class T>
void input_parser::read(T & nr){
    char c;
    int semn=1;
    nr=0;
    c=this->next();
    while(!isdigit(c) && c!='-')
        c=this->next();
    while(c=='-')
        c=this->next(),semn*=-1;
    while(isdigit(c))
        nr=nr*10+c-'0',c=this->next();
    nr*=semn;
}
template<class T,typename ... Args>
void input_parser::read(T & t,Args&...args){
    read(t);
    read(args...);
}

void input_parser::read(char *chp,size_t sz){
    char c;
    c=next();
    while(c==' ' || c=='\n')
        c=next();
    for(size_t i=0;i<sz && c!=' ' && c!='\n';i++)
        chp[i]=c,c=next();
}

input_parser in("heapuri.in");
std::ofstream out("heapuri.out");
std::vector<int>v;
int main(){
    int n,t,aux;
    in.read(n);
    bst=NULL;
    for(int i=1;i<=n;i++){
        in.read(t);
        if(t==3)
            out<<minb(bst)->val<<'\n';
        else{
            in.read(aux);
            if(t==1){
                if(bst==NULL)
                    bst=insert(bst,aux);
                else
                    insert(bst,aux);
                v.push_back(aux);
            }
            else{
                bst=erase(v[aux-1],bst);

            }
        }
    }
    return 0;
}