Cod sursa(job #1291302)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 12 decembrie 2014 18:12:02
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>

using namespace std;

class treap {
public:
    short int key;
    short int priority;
    short int din;

    treap *left,*right;

    treap (short int key=0, short int priority=0, short int din=0, treap *left=NULL, treap *right=NULL): key(key), priority(priority), din(din), left(left), right(right) {}
}*rad,*nil;

inline void calc_din(treap* &x) {
    if(x==nil)
        return;
    x->din=x->left->din+x->right->din+1;
}

inline void right_rotation(treap* &x) {
    treap *y=x->left;
    x->left=y->right;
    y->right=x;

    x=y;
    calc_din(x->left);
    calc_din(x->right);
    calc_din(x);
}

inline void left_rotation(treap* &y) {
    treap *x=y->right;
    y->right=x->left;
    x->left=y;

    y=x;
    calc_din(y->left);
    calc_din(y->right);
    calc_din(y);
}

void balance(treap* &t){
    if((t->priority)<(t->left->priority))
        right_rotation(t);
    else if(t->priority<t->right->priority)
        left_rotation(t);
    else
        calc_din(t);
}

short int concurent;
void insert(treap* &t,short int val){
    if(t==nil){
        t=new treap(concurent,rand()%30000+1,1,nil,nil);
        return;
    }

    if(val==1)
        insert(t->left,val);
    else if(t->left->din+1>=val)
        insert(t->left,val);
    else
        insert(t->right,val-t->left->din-1);
    balance(t);
}

//ofstream cout("schi.out");
void parcurge(treap* &t) {
    if(t==nil)
        return;

    parcurge(t->left);
    //cout<<t->key<<'\n';
    printf("%hd\n",t->key);

    parcurge(t->right);
}

int main()
{
    //ifstream cin("schi.in");
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);

    srand(25);

    short int n=0;
    //cin>>n;
    scanf("%hd",&n);

    short int x;
    //cin>>x;
    scanf("%hd",&x);

    nil=new treap(0,0,0);
    nil->left=nil;
    nil->right=nil;

    rad=new treap(1,rand()%30000+1,1,nil,nil);

    for(int i=2;i<=n;i++){
        //cin>>x;
        scanf("%hd",&x);

        concurent=i;
        insert(rad,x);
    }

    parcurge(rad);

    //cin.close();
    //cout.close();
    return 0;
}