Cod sursa(job #2747047)

Utilizator HadircaDionisieHadirca Dionisie HadircaDionisie Data 28 aprilie 2021 19:47:53
Problema Schi Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
// Bst_noduri_arbori_Nebunii.cpp : This file contains the 'main' function. Program execution begins and ends there.
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("schi.in");
ofstream fout("schi.out");

struct Node {
	pair<int, int> val;
	Node* left;
	Node* right;
	int leftHeavy = 0;
	Node(int index = 0, int loc = 0) {
		val.first = index;
		val.second = loc;
		left = NULL;
		right = NULL;
	}
};

Node* updateRight(Node* root, int x) {
	if (root != NULL) {
		root->val.second += x;
		updateRight(root->left, x);
		updateRight(root->left, x);
	}
	return root;
}

Node* insert(Node* root, int index, int loc) {
	int cnt = 0;
	if (root == NULL)
	{
		Node* y = new Node(index, loc);
		return y;
	}
	if (loc <= root->val.second) {
		cnt++;
		root->leftHeavy++;
		root->val.second++;
		root->left = insert(root->left, index, loc);
	}
	else {
		root->right = insert(root->right, index, loc);
	}
	updateRight(root->right,cnt);
	return root;
}

void inorder(Node* root) {
	if (root == NULL)
		return;
	inorder(root->left);
	fout << root->val.first<<'\n';
	inorder(root->right);
}

int main()
{
	int n, loc;
	fin >> n;
	fin >> loc;
	Node* root = new Node(1,loc);
	for (int i = 2; i <= n; i++) {
		fin >> loc;
		insert(root,i,loc);
	}
	inorder(root);
}