Cod sursa(job #1847669)

Utilizator dan89Stan Alexandru dan89 Data 14 ianuarie 2017 20:46:42
Problema Schi Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <iostream>
#define in "schi.in"
#define out "schi.out"
#define maxn 30005

struct tree {
    tree *left;
    tree *right;
    int st;
    int dr;
    int position;
};

int rez[maxn];

tree* updateTree(tree *node, int left, int right, int member, int pos) {
    if ( node==NULL ) {
        node = new tree;
        node->left = NULL;
        node->right = NULL;
        node->st = left;
        node->dr = right;
        node->position = 0;
    }

    if (node->st==node->dr) {
        node->position = 1;
        rez[node->st] = member;
        return node;
    }

    int mid = (node->st+node->dr) / 2;

    int p = 0;

    if (node->left != NULL && node->left->position > 0) {
        p = node->left->position;
    }

    if (pos <= mid - p) {
        node->left = updateTree(node->left, node->st, mid, member, pos);
    } else {
        node->right = updateTree(node->right, mid+1, node->dr, member, pos+p);
    }
    node->position = ((node->left != NULL) ? node->left->position : 0) +
            ((node->right != NULL) ? node->right->position : 0);

    return node;
}


int main() {
    freopen(in, "r", stdin);
    freopen(out, "w", stdout);

    int N;
    scanf("%d", &N);

    tree *root = NULL;
    int v[maxn];
    for (int i=1; i<=N; i++) {
        scanf("%d", &v[i]);
    }

    for (int i =N; i>0; --i) {
        root = updateTree(root,1, N, i, v[i]);
    }
    for (int i=1; i<=N; i++) {
        printf("%d\n", rez[i]);
    }
    return 0;
}