Cod sursa(job #1291208)

Utilizator dariusdariusMarian Darius dariusdarius Data 12 decembrie 2014 15:30:05
Problema Schi Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <algorithm>
#include <fstream>
using namespace std;

struct Treap {
    short value, dp; int priority;
    Treap *left, *right;
    Treap() {}
    Treap(short vvalue, short ddp, int ppriority, Treap* lleft, Treap *rright) {
        value = vvalue;
        dp = ddp;
        priority = ppriority;
        left = lleft; right = rright;
    }
} *root, *NIL;

void dfs(const Treap* node, ofstream &fout, bool f) {
    if (node->left != NIL) {
        dfs(node->left, fout, f);
    }
    if (f) {
        fout << node->value << "\n";// << " " << node->dp << "\n";
    } else {
    }
    if (node->right != NIL) {
        dfs(node->right, fout, f);
    }
}

void rotate_left(Treap* &node) {
    Treap *x = node->left->left, *y = node->left->right, *z = node->right, *a = node, *b = node->left;
    node = b;
    node->left = x;
    node->right = a;
    node->right->left = y;
    node->right->right = z;
    node->right->dp = y->dp + z->dp + 1;
    node->dp = node->left->dp + node->right->dp + 1;
}

void rotate_right(Treap* &node) {
    Treap *x = node->left, *y = node->right->left, *z = node->right->right, *b = node, *a = node->right;
    node = a;
    node->left = b;
    node->right = z;
    node->left->left = x;
    node->left->right = y;
    node->left->dp = x->dp + y->dp + 1;
    node->dp = node->left->dp + node->right->dp + 1;
}

void balance(Treap* &node) {
    if (node->left->priority > node->priority) {
        rotate_left(node);
    } else if (node->right->priority > node->priority) {
        rotate_right(node);
    }
    node->dp = node->left->dp + node->right->dp + 1;
}

void insert(Treap* &node, short value, short key, int priority) {
    if (node == NIL) {
        node = new Treap(value, 1, priority, NIL, NIL);
        return;
    }
    if (node->left->dp >= key) {
        insert(node->left, value, key, priority);
    } else {
        insert(node->right, value, key - node->left->dp - 1, priority);
    }
    balance(node);
}

int main() {
    ifstream fin("schi.in");
    ofstream fout("schi.out");
    int n; short x;
    fin >> n >> x;
    NIL = new Treap(0, 0, 0, NULL, NULL);
    root = new Treap(1, 1, rand() + 1, NIL, NIL);
    for (short i = 2; i <= n; ++ i) {
        fin >> x;
        //cout << "Before inserting " << i << "\n";
        //dfs(root, fout, false);
        insert(root, i, x - 1, rand() + 1);
    }
    dfs(root, fout, true);
    return 0;
}