Cod sursa(job #229892)

Utilizator MariusMarius Stroe Marius Data 12 decembrie 2008 00:06:30
Problema Schi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 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 != NULL ? n->l->cnt : 0) + (n->r != NULL ? n->r->cnt : 0))

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

void insert(T* &n, int lo, int hi)
{
    if (hi < lo)  return ;
    int mid = (hi + lo) >> 1;
    n = new T(mid);
    insert(n->l, lo, mid - 1);
    insert(n->r, mid + 1, hi);
    getc(n);
}

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

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

int main(void)
{
    srand(unsigned(time(NULL)));
    R = NULL;

    freopen(iname, "r", stdin);
    int V[30000];
    int n;

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

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

    return 0;
}