Cod sursa(job #2533112)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 28 ianuarie 2020 19:25:12
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.53 kb
#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();
	
}