Cod sursa(job #2522570)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 12 ianuarie 2020 18:04:14
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.25 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("schi.in");
ofstream out("schi.out");
 
template < typename T >
class AVL_Vector {
private:
	struct Node {
		int size, depth; T val;
		Node *left, *right;
		
		Node() {
			depth = size = 1;
			left = right = nullptr;
		}
	};
	
	int get_size(Node *r) {
		if(r == nullptr) return 0;
		return r->size;
	}
	
	int get_depth(Node *r) {
	    if(r == nullptr) return 0;
	    return r->depth;
	}
	
	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;
	}
	
	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;
	}
	
	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);
		root->depth = max(get_depth(root->left), get_depth(root->right)) + 1;
	}
	
	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;
	}
	
	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;
		inord(root->right);
	}
	
	Node *head;
public:
	AVL_Vector<T>() {
		head = nullptr;
	}
	
	int size() {
		return get_size(head);
	}
	
	int depth() {
	    return get_depth(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);
	}
	
	int minimum(void) {
		return get_min(head);
	}
	
	void inorder() {
		inord(head); out << endl;
	}
};

int main() {
	AVL_Vector<int> v;
	
	int n; in >> n;
	for(int i = 1; i <= n; i++) {
		int rd; in >> rd;
		v.insert(rd-1, i);
	}
	
	v.inord();
}