Cod sursa(job #2418274)

Utilizator mihai2003LLL LLL mihai2003 Data 4 mai 2019 15:26:59
Problema Heapuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.91 kb
#include <iostream>
#include <fstream>
#include <cstring>

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();
}

class Node
{
public:
    Node *left,*right;
    int key,_height;
    int height()
    {
        if(this==NULL)
            return 0;
        return _height;
    }
    Node(int k)
    {
        key=k;
        _height=1;
        left=right=NULL;
    }
};

Node *right_rotate(Node * y)
{
    Node * aux=y->left;
    Node * t2=aux->right;
    aux->right=y;
    y->left=t2;
    y->_height=std::max(y->left->height(),y->right->height())+1;
    aux->_height=std::max(aux->left->height(),aux->right->height())+1;
    return aux;
}

Node *left_rotate(Node *x)
{
    Node *y=x->right;
    Node *t2=y->left;
    y->left=x;
    x->right=t2;
    x->_height=std::max(x->left->height(),x->right->height())+1;
    y->_height=std::max(y->left->height(),y->right->height())+1;
    return y;
}

int get_balance(Node *n)
{
    if(n==NULL)
        return 0;
    return n->left->height()-n->right->height();
}

Node *insert(Node *node,int key)
{
    if(node==NULL)
        return new Node(key);
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else
        return node;
    node->_height =1+std::max(node->left->height(),node->right->height());
    int balance = get_balance(node);
    if (balance > 1 && key < node->left->key)
        return right_rotate(node);
    if (balance < -1 && key > node->right->key)
        return left_rotate(node);
    if (balance > 1 && key > node->left->key)
    {
        node->left = left_rotate(node->left);
        return right_rotate(node);
    }
    if (balance < -1 && key < node->right->key)
    {
        node->right = right_rotate(node->right);
        return left_rotate(node);
    }
    return node;
}

Node * minValueNode(Node* node)
{
    Node* current = node;
    while (current->left != NULL)
        current = current->left;
    return current;
}

Node* deleteNode(Node* root, int key)
{
    if (root == NULL)
        return root;
    if ( key < root->key )
        root->left = deleteNode(root->left, key);
    else if( key > root->key )
        root->right = deleteNode(root->right, key);
    else
    {
        if( (root->left == NULL) ||
                (root->right == NULL) )
        {
            Node *temp = root->left ?
                         root->left :
                         root->right;
            if (temp == NULL)
            {
                temp = root;
                root = NULL;
            }
            else
                *root = *temp;
            delete temp;
        }
        else
        {
            Node* temp = minValueNode(root->right);
            root->key = temp->key;
            root->right = deleteNode(root->right,
                                     temp->key);
        }
    }
    if (root == NULL)
        return root;
    root->_height = 1 + std::max(root->left->height(),
                           root->right->height());
    int balance = get_balance(root);
    if (balance > 1 &&
            get_balance(root->left) >= 0)
        return right_rotate(root);
    if (balance > 1 &&
            get_balance(root->left) < 0)
    {
        root->left = left_rotate(root->left);
        return right_rotate(root);
    }

    if (balance < -1 &&
            get_balance(root->right) <= 0)
        return left_rotate(root);
    if (balance < -1 &&
            get_balance(root->right) > 0)
    {
        root->right = right_rotate(root->right);
        return left_rotate(root);
    }

    return root;
}
input_parser in("heapuri.in");
std::ofstream out("heapuri.out");
#include <vector>
std::vector<int>v;
int main()
{
    Node *bst=NULL;
    int n,t,aux;
    in.read(n);
    for(int i=1;i<=n;i++){
        in.read(t);
        if(t==3)
            out<<minValueNode(bst)->key<<'\n';
        else{
            in.read(aux);
            if(t==1){
                if(bst==NULL)
                    bst=insert(bst,aux);
                else
                    bst=insert(bst,aux);
                v.push_back(aux);
            }
            else{
                bst=deleteNode(bst,v[aux-1]);

            }
        }
    }

    return 0;
}