Cod sursa(job #2522578)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 12 ianuarie 2020 18:08:01
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.93 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; 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;
	}

	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);
	}

	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);
	}

	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); 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.inorder();
}