Cod sursa(job #2409185)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 18 aprilie 2019 19:25:46
Problema Order Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.01 kb
#include <fstream>
#include <stdlib.h>
#include <time.h>

using namespace std;

ifstream fin  ("order.in");
ofstream fout ("order.out");

int nr,i,n,nr_nodes,sol;
struct treap{
    int val;
    int priority;
    int nr;
    treap *left, *right;
    treap (int val, int priority, treap *left, treap*right, int nr){
        this->val = val;
        this->priority = priority;
        this->left = left;
        this->right = right;
        this->nr = nr;
    }
};
treap *rad, *nil;

void get_nr (treap *rad){
   rad->nr = rad->left->nr + rad->right->nr + 1;
}

void rotate_left (treap *&rad){
    treap *aux = rad->left;
    rad->left = aux->right;
    aux->right = rad;
    rad = aux;
    get_nr (rad->right);
    get_nr (rad);
}
void rotate_right (treap *&rad){
    treap *aux = rad->right;
    rad->right = aux->left;
    aux->left = rad;
    rad = aux;
    get_nr (rad->left);
    get_nr (rad);
}
void balance (treap *&rad){
    if (rad->left != NULL && rad->left->priority > rad->priority)
        rotate_left (rad);
    else
        if (rad->right != NULL && rad->right->priority > rad->priority)
            rotate_right(rad);
}

void add_node (treap *&rad, int key, int priority){
    if (rad == nil){
        rad = new treap (key,priority,nil,nil,1);
        nr_nodes++;
        return;
    } else {
        if (rad->val > key)
            add_node(rad->left,key,priority);
        else
            if (rad->val < key)
                add_node(rad->right,key,priority);
    }
    balance (rad);
    get_nr (rad);

}

void delete_node (treap *&rad, int key){
    if (rad != nil){
        if (rad->val > key)
            delete_node (rad->left,key);
        else{
            if (rad->val < key)
                delete_node (rad->right,key);
            else { /// inseamna ca am gasit valoarea
                if (rad->left == nil && rad->right == nil){ /// ins ca e frunza
                    delete rad;
                    rad = nil;
                    nr_nodes--;
                } else {
                    if (rad->left->priority > rad->right->priority)
                        rotate_left (rad);
                    else rotate_right (rad);
                    delete_node (rad,key);
                }

            }
        }
        if (rad != nil) /// trebuie sa updatez iar mini, maxi si dif
            get_nr (rad);
    }
}

int query (treap *&rad, int nr){
    if (rad->left->nr == nr-1)
        return rad->val;
    else{
        if (rad->left->nr < nr)
            return query (rad->right, nr-rad->left->nr-1);
        else return query (rad->left,nr);
    }
}


int main (){

    srand( time(0) );
    rad = nil = new treap (0,0,NULL,NULL,0);
    fin>>n;
    for (i=1;i<=n;i++)
        add_node (rad,i,rand());
    nr = 2;
    for (i=0;i<n;i++){
        nr += i;
        nr %= (n-i);
        if (nr == 0)
            nr = n-i;
        sol = query(rad,nr);
        fout<<sol<<" ";
        delete_node (rad,sol);
    }

    return 0;
}