Cod sursa(job #1477813)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 27 august 2015 02:18:18
Problema Schi Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.71 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);

short int v[30001];
short int ans[30001];
int n;

struct treap {

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

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

            this->key = key, this->priority = priority, this->total = 1;
            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, 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, NULL, NULL);
    empty->total = root->total = 0;
}

int main() {

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

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

    int N = n, add, left, right, mid, sol;
    for(; n; --n) {

        left = v[n], right = N, sol = v[n];
        while(left <= right) {

            mid = (left + right) >> 1, add = under_key(root, mid);
            if(v[n] + add <= mid)
                sol = mid, right = mid - 1;
            else
                left = mid + 1;
        }


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

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