Cod sursa(job #226133)

Utilizator stef2nStefan Istrate stef2n Data 1 decembrie 2008 01:03:42
Problema Schi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <fstream>
using namespace std;

ifstream in("schi.in");
ofstream out("schi.out");

class Treap {
private:
    class Node {
    public:
        short int key, cnt, pr;
        Node *left, *right;

        Node(int _key) {
            key = _key, cnt = 1, pr = rand() % 31013;
            left = right = NULL;
        }
    };

    void insert(Node *&, Node *&, int);
    int recount(Node *);
    void rotleft(Node *&);
    void rotright(Node *&);
    void balance(Node *&);
    void write(Node *);

public:
    Node *root;

    Treap(): root(NULL) {
        srand(time(0));
    }

    void insert(int key, int pos) {
        Node *p = new Node(key);
        insert(root, p, pos);
    }

    void write() {
        write(root);
    }
};

void Treap::insert(Node *&p, Node *&q, int pos) {
    if(p == NULL) {
        p = q;
        return;
    }
    int t = (p->left == NULL ? 0 : p->left->cnt);
    if(pos <= t + 1)
        insert(p->left, q, pos);
    else
        insert(p->right, q, pos - t - 1);
    balance(p);
}

int Treap::recount(Node *p) {
    return 1 + (p->left == NULL ? 0 : p->left->cnt) + (p->right == NULL ? 0 : p->right->cnt);
}

void Treap::rotleft(Node *&p) {
    Node *q = p->right;
    p->right = q->left, q->left = p;
    p->cnt = recount(p), q->cnt = recount(q);
    p = q;
}

void Treap::rotright(Node *&p) {
    Node *q = p->left;
    p->left = q->right, q->right = p;
    p->cnt = recount(p), q->cnt = recount(q);
    p = q;
}

void Treap::balance(Node *&p) {
    if(p->left && p->pr < p->left->pr)
        rotright(p);
    else
        if(p->right && p->pr < p->right->pr)
            rotleft(p);
        else
            p->cnt = recount(p);
}

void Treap::write(Node *p) {
    if(!p)
        return;
    write(p->left);
    out << p->key << '\n';
    write(p->right);
}


int main() {
    int N, pos;
    Treap T;

    in >> N;
    for(int i = 1; i <= N; ++i) {
        in >> pos;
        T.insert(i, pos);
    }

    T.write();

    return 0;
}