Cod sursa(job #1574605)

Utilizator cautionPopescu Teodor caution Data 20 ianuarie 2016 18:23:38
Problema Schi Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <fstream>
#define MAX_N 30005
//build an order statistics tree
//use sentinel (with key=0, size=0, left=nullptr and right=nullptr)

struct OrderStatisticsNode
{
    int key, size;
    OrderStatisticsNode *parent, *left, *right;
    OrderStatisticsNode(int x) :
        key(x), size(0), parent(nullptr), left(nullptr), right(nullptr)
    {}
};

int final_rank[MAX_N];
OrderStatisticsNode* kNullNode;

void os_insert(OrderStatisticsNode* p, int key, int order)
{
    if(order <= p->left->size+1) {
        if(p->left->key == 0) { //sentinel so we insert here
            p->left = new OrderStatisticsNode(key);
            p->left->size = 1;
            p->left->parent = p;
            p->left->left = kNullNode;
            p->left->right = kNullNode;
        }
        else os_insert(p->left, key, order);
    }
    else {
        if(p->right->key == 0) { //sentinel so we insert here
            p->right = new OrderStatisticsNode(key);
            p->right->size = 1;
            p->right->parent = p;
            p->right->left = kNullNode;
            p->right->right = kNullNode;
        }
        else os_insert(p->right, key, order-p->left->size-1);
    }
    p->size = p->left->size+p->right->size+1;
}
void os_inorder_walk(OrderStatisticsNode* p, int offset)
{
    if(p->size == 0) return;
    final_rank[offset+p->left->size+1] = p->key;
    os_inorder_walk(p->left, offset);
    os_inorder_walk(p->right, offset+p->left->size+1);
}
int main()
{
    int n, aux;
    OrderStatisticsNode* root;
    std::ifstream in("schi.in");
    std::ofstream out("schi.out");
    in>>n;
    in>>aux;
    kNullNode = new OrderStatisticsNode(0);
    root = new OrderStatisticsNode(1);
    root->size = 1;
    root->parent = kNullNode;
    root->left = kNullNode;
    root->right = kNullNode;
    for(int i=2; i<=n; ++i) {
        in>>aux;
        os_insert(root, i, aux);
    }
    os_inorder_walk(root, 0);
    for(int i=1; i<=n; ++i) out<<final_rank[i]<<'\n';
    return 0;
}