Cod sursa(job #1477803)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 27 august 2015 01:46:43
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
/**
  *  Worg
  */
#include <ctime>
#include <cstdio>
#include <cstdlib>

using namespace std;
FILE *fin=freopen("schi.in","r",stdin);
FILE *fout=freopen("schi.out","w",stdout);

int v[30030], ans[30300];
int n;

struct treap {

        int key, priority, total;
        treap *left, *right;

        treap(int key, int priority, int cnt, treap *left, treap *right) {

            this->key = key, this->priority = priority, this->total = cnt;
            this->left = left, this->right = right;

        }
} *root, *empty;

void update(treap *&node) {

    if(node == empty)
        node->total = 0;
    else
        node->total = node->left->total + node->right->total + 1;
}

void rotLeft(treap *&node) {

    treap *T = node->left;
    node->left = T->right, T->right = node;
    node = T;

    update(node->right); update(node);
}

void rotRight(treap *&node) {

    treap *T = node->right;
    node->right = T->left, T->left = node;
    node = T;

    update(node->left); update(node);
}

void balance(treap *&node) {

    if(node->priority < node->left->priority)
        rotLeft(node);
    else if(node->priority < node->right->priority)
        rotRight(node);
}

void insert(treap *&node, int key) {

    if(node == empty) {

        node = new treap(key, rand() + 1, 1, empty, empty);
        update(node);
        return;
    }

    if(node->key > key)
        insert(node->left, key);
    else
        insert(node->right, key);

    update(node);
    balance(node);
}

int under_key(treap *&node, int key) {

    if(node == empty)
        return 0;
    if(node->key < key)
        return node->left->total + 1 + under_key(node->right, key);
    if(node->key == key)
        return node->left->total + 1;

    return under_key(node->left, key);
}

void write(treap *node) {

    if(node == empty)
        return;
    write(node->left);
    printf("%d ", node->key);
    write(node->right);
}

void init() {

    srand(unsigned(time(0)));
    empty = root = new treap(0, 0, 0, NULL, NULL);
}

int main() {

    init();
    scanf("%d ", &n);

    for(int i = 1; i <= n; ++i)
        scanf("%d ", &v[i]);

    int pos, N = n, last, add;
    for(; n; --n) {

        add = 0, pos = v[n];

        do {

            last = add;
            add = under_key(root, pos);
            pos += add - last;
        }while(add != last);

        ans[pos] = n;
        insert(root, pos);
    }

    for(int i = 1; i <= N; ++i)
        printf("%d\n", ans[i]);
    return 0;
}