Pagini recente » Cod sursa (job #485568) | Cod sursa (job #2472690) | Cod sursa (job #2282802) | Solutii preONI 2006, Runda a 4-a | Cod sursa (job #2533112)
#include <bits/stdc++.h>
using namespace std;
FILE *in = fopen("schi.in", "r");
FILE *out = fopen("schi.out", "w");
template < typename T >
class AVL_Vector {
private:
struct Node {
int size; T val;
Node *left, *right;
Node() {
size = 1;
left = right = nullptr;
}
};
inline int get_size(Node *r) {
if(r == nullptr) return 0;
return r->size;
}
inline Node *rotateLeft(Node *x) {
Node *y = x->right, *T2;
if(y == nullptr) T2 = nullptr;
else T2 = y->left;
x->right = T2;
y->left = x;
return y;
}
inline Node *rotateRight(Node *y) {
Node *x = y->left, *T2;
if(x == nullptr) T2 = nullptr;
else T2 = x->right;
x->right = y;
y->left = T2;
return x;
}
inline void level_refresh(Node *root, int lev) {
if(lev < 0 || root == nullptr) return;
level_refresh(root->left, lev-1);
level_refresh(root->right, lev-1);
root->size = get_size(root->left) + 1 + get_size(root->right);
}
inline Node *balance_left(Node *root) {
///Asume the left node is empty, do rotations down the left path until everything is balanced
if(root == nullptr) return nullptr;
if(root->right == nullptr) return root;
root = rotateLeft(root);
root->left = balance_left(root->left);
level_refresh(root, 1);
return root;
}
inline Node *ins(Node *root, int rank, T &_val) {
if(root == nullptr) {
Node *tmp = new Node;
tmp->val = _val;
return tmp;
}
if(rank == get_size(root->left)) {
Node *tmp = new Node;
tmp->val = _val;
tmp->left = root->left;
tmp->right = root;
root->left = nullptr;
tmp->right = balance_left(tmp->right);
level_refresh(root, 1);
return tmp;
}
if(rank < get_size(root->left)) {
root->left = ins(root->left, rank, _val);
if(get_size(root->left) > get_size(root->right) + 1) {
root = rotateRight(root);
}
}
else {
root->right = ins(root->right, rank - 1 - get_size(root->left), _val);
if(get_size(root->left) + 1 < get_size(root->right)) {
root = rotateLeft(root);
}
}
level_refresh(root, 1);
return root;
}
T &acc(Node *root, int rank) {
if(rank == get_size(root->left)) return root->val;
if(rank < get_size(root->left)) return acc(root->left, rank);
else return acc(root->right, rank - 1 - get_size(root->left));
}
void inord(Node *root) {
if(root == nullptr) return;
inord(root->left);
//out << root->val << endl;
fprintf(out, "%d\n", root->val);
inord(root->right);
}
Node *head;
public:
AVL_Vector<T>() {
head = nullptr;
}
int size() {
return get_size(head);
}
void insert(int rank, T &val) {
head = ins(head, rank, val);
}
T& access(int rank) {
return acc(head, rank);
}
T& operator [](int rank) {
return acc(head, rank);
}
void inorder() {
inord(head);
}
};
int main() {
AVL_Vector<int> v;
int n;
fscanf(in, "%d", &n);
for(int i = 1; i <= n; i++) {
int rd; fscanf(in, "%d", &rd);
v.insert(rd-1, i);
}
v.inorder();
}