Cod sursa(job #223799)

Utilizator MariusMarius Stroe Marius Data 29 noiembrie 2008 13:55:37
Problema Schi Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const char iname[] = "schi.in";
const char oname[] = "schi.out";

#define getc(n)  (n->cnt = (!n->el) + n->l->cnt + n->r->cnt)

struct T {
    int key, pr;
    int cnt, el;
    T *l, *r;
    T() {}
    T(int key, int pr, T *l, T *r) {
        this->key = key, this->pr = pr,
                this->l = l, this->r = r;
        cnt = el = 0;
    }
} *R, *nil;


void init(T* &R)
{
    srand(unsigned(time(NULL)));
    R = nil = new T(0, 0, NULL, NULL);
}

void rotleft(T* &n)
{
    T *t = n->l;
    n->l = t->r, t->r = n, getc(n), getc(t), n = t;
}

void rotright(T* &n)
{
    T *t = n->r;
    n->r = t->l, t->l = n, getc(n), getc(t), n = t;
}

void balance(T* &n)
{
    if (n->l->pr > n->r->pr)
        rotleft(n);
    else if (n->r->pr > n->l->pr)
        rotright(n);
    getc(n);
}

void insert(T* &n, int key)
{
    if (n == nil) {
        n = new T(key, rand() + 1, nil, nil);
        getc(n);
        return ;
    }
    if (key < n->key)
        insert(n->l, key);
    if (key > n->key)
        insert(n->r, key);
    balance(n);
}

void lookup(T* &n, int cnt, int el)
{
    if (cnt <= n->l->cnt)
        lookup(n->l, cnt, el);
    else {
        if (n->l->cnt + (!n->el) == cnt)
            n->el = el;
        else
            lookup(n->r, cnt - (n->l->cnt + (!n->el)), el);
    }
    getc(n);
}

void print(T* &n) {
    if (n == nil)  return ;
    print(n->l), printf("%d\n", n->el), print(n->r);
}

int main(void)
{
    init(R);
    freopen(iname, "r", stdin);
    vector <int> V;
    int n;

    scanf("%d", &n);
    V.resize(n);
    for (int i = 0; i < n; ++ i) {
        scanf("%d", &V[i]);
        insert(R, i);
    }
    for (int i = n - 1; i >= 0; -- i)
        lookup(R, V[i], i + 1);

    freopen(oname, "w", stdout);
    print(R);

    return 0;
}