Pagini recente » Cod sursa (job #2169677) | Cod sursa (job #1003840) | Cod sursa (job #2583491) | Cod sursa (job #940418) | Cod sursa (job #1574605)
#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;
}