#include <iostream>
using namespace std;
const int MAX_NODE = 18000;
const int HASH_SIZE = 30000;
struct Node{
Node* parent;
Node* child[3];
int num;
bool valid;
}NodePool[MAX_NODE];
int PoolCnt, GroupCnt;
struct HashNode{
int key;
Node* data;
}HashTbl[HASH_SIZE];
void hashAdd(int key, Node* data){
unsigned long h = key % HASH_SIZE;
while (HashTbl[h].key != 0)
{
if(HashTbl[h].key == key){
HashTbl[h].data = data;
return;
}
h = (h + 1) % HASH_SIZE;
}
HashTbl[h].key = key;
HashTbl[h].data = data;
}
Node* hashFind(int key){
unsigned long h = key % HASH_SIZE;
int cnt = HASH_SIZE;
while (HashTbl[h].key != 0 && cnt--)
{
if(HashTbl[h].key == key){
return HashTbl[h].data;
}
h = (h + 1) % HASH_SIZE;
}
return nullptr;
}
void delNode(Node* node){
if(node == nullptr)return;
node->valid = false;
for(int i = 0; i < 3; ++i){
delNode(node->child[i]);
}
}
void init(int N, int mId[], int nNum[]){
PoolCnt = 0;
for(int i = 0; i < HASH_SIZE; ++i){
HashTbl[i].key = 0;
}
GroupCnt = N;
for(int i = 0; i < N; ++i){
Node* node = &NodePool[PoolCnt++];
hashAdd(mId[i], node);
node->valid = true;
node->parent = nullptr;
node->child[0] = node->child[1] = node->child[2] = nullptr;
node->num = nNum[i];
}
}
int add(int mId, int nNum, int mParent){
Node* node = &NodePool[PoolCnt++];
Node* parent = hashFind(mParent);
if(parent->child[0] == nullptr){
parent->child[0] = node;
}
else if(parent->child[1] == nullptr){
parent->child[1] = node;
}
else if(parent->child[2] == nullptr){
parent->child[2] = node;
}
else{
return -1;
}
Node* curr = parent;
while (curr)
{
curr->num += nNum;
curr = curr->parent;
}
hashAdd(mId, node);
node->valid = true;
node->parent = parent;
node->child[0] = node->child[1] = node->child[2] = nullptr;
node->num = nNum;
return parent->num;
}
int remove(int mId){
Node* node = hashFind(mId);
if(node == nullptr || node->valid == false){
return -1;
}
Node* parent = node->parent;
if(parent->child[0] == node){
parent->child[0] = nullptr;
}
else if(parent->child[1] == node){
parent->child[1] = nullptr;
}
else if(parent->child[2] == node){
parent->child[2] = nullptr;
}
Node* curr = parent;
while (curr)
{
curr->num-=node->num;
curr = curr->parent;
}
delNode(node);
return node->num;
}
int distribute(int K){
int low = 1, high = 0;
for(int i = 0; i < GroupCnt; ++i){
if(NodePool[i].num > high){
high = NodePool[i].num;
}
};
while (low <= high)
{
int mid = (low + high)/2;
int sum = 0;
for(int i = 0; i < GroupCnt; ++i){
if(NodePool[i].num <= mid){
sum += NodePool[i].num;
}
else{
sum += mid;
}
}
if(sum <= K){
low = mid + 1;
}
else{
high = mid - 1;
}
}
return high;
}
int main(){
int mId[] = {7, 4, 2};
int mNum[] = {25, 5, 40};
init(3, mId, mNum);
std::cout << add(3, 5, 4) << endl;//10
std::cout << add(9, 5, 7) << endl;//30
std::cout << add(1, 15, 4) << endl;//25
std::cout << add(8, 10, 1) << endl;//25
std::cout << distribute(100) << endl;//35
std::cout << add(6, 20, 4) << endl;//55
std::cout << distribute(109) << endl;//39
std::cout << add(5, 20, 9) << endl;//25
std::cout << distribute(131) << endl;//45
std::cout << remove(1) << endl;//25
std::cout << distribute(110) << endl;//40
init(3, mId, mNum);
return 0;
}