Untitled

Each of N groups has multiple departments which make up a single tree.

A department has an ID, information about the number of employees of the department and a maximum of three sub-departments.

You are required to give out gift cards to N groups in accordance with the number of employees of each group.
There are a total of K gift cards. The rule for giving out gift cards is as follows.

1. If the total number of employees is less than or equals to K, hand out gift cards in accordance with the number of employees of each group.
2. If the total number of employees is greater than K, decide the upper limit L.
   If the number of employees of a group is less than or equals to L, give out gift cards in accordance with the number of employees of each group.
   If the number of employees of a group is greater than L, hand out L gift cards.

You are required to find the greatest number among the number of gift cards given out to each group after you hand out as many gift cards as possible, but not more than K.

[Fig. 1] is an example of three given groups. The number inside each circle represents the number of employees of a department.
The first, second, and third groups have 30, 35, and 40 employees, respectively.



[Fig. 1]

If there are 105 or more gift cards, gift cards can be given out according to the number of employees of each group.
The greatest number among the number of gift cards given out to each group is 40.

If there are 100 gift cards, you are required to decide the upper limit because the total number of employees is greater than the number of gift cards.
If you choose 35 as the upper limit, you can hand out 30 and 35 gift cards to the first and second groups.
As the third group has more than 35 employees, you can hand out only 35 gift cards.
This is the way to give as many gift cards as possible, and the greatest number among the number of gift cards given out to each group is 35.

 

Implement each required function by referring to the following API description.

※ The function signature below is based on C/C++. As for other languages, refer to the provided Main and User Code.

 

The following is the description of API to be written in the User Code. 

void init(int N, int mId[], int mNum[])

This function is called in the beginning of each test case.

For each of N groups, the ID of the topmost department and the number of employees of the department are given as arrays.

 

Parameters

N: the number of groups ( 3 ≤ N ≤ 1,000 )

 

As for all i(s) which are (0 ≤ i ＜ N),

mId[i]: the ID of the topmost department of the (i+1)th group ( 1 ≤ mId[i] ≤ 1,000,000,000 )

mNum[i]: the number of employees of the department ( 1 ≤ mNum[i] ≤ 100 )

int add(int mId, int mNum, int mParent)

Add department mId as the sub-department of department mParent.

The number of employees of department mId is mNum.

mParent is always an ID of an existing department.

If mParent has three sub-departments already, adding of the department fails, and -1 is returned.

The ID of an already-existing department is never given as mId.

 

Parameters

mId: the ID of a department ( 1 ≤ mId ≤ 1,000,000,000 )

mNum: the number of employees of a department ( 1 ≤ mNum ≤ 100 )

mParent: the ID of the higher-level department ( 1 ≤ mParent ≤ 1,000,000,000 )

 

Returns

If a department is added successfully, return the sum of the number of employees of department mParent and all departments below mParent. In other words, return the sum of the number of employees of the sub-tree that has mParent as the root node.

If adding fails, return -1.

int remove(int mId)

Delete the department with the ID of mId. All departments below department mId are deleted together.

The ID of the topmost department is never given.

The ID of an already-deleted department may be given.

If department mId does not exist, return -1.

 

Parameters

mId: the ID of the department ( 1 ≤ mId ≤ 1,000,000,000 )

 

Returns

If department mId exists, return the sum of the number of employees of mId and all departments below it. In other words, return the sum of the number of employees of the sub-tree whose root note is mId.
If not, return -1.

int distribute(int K)

Return the greatest number among the number of gift cards handed out to each group, when K gift cards are given out as many as possible to N groups, following the rule for giving out gift cards.

 

Parameters

K: the number of gift cards ( N ≤ K ≤ 800,000 )

 

Returns

Return the greatest number among the number of gift cards given out to each group.

 

[Example]

Think of the following case in [Table 1].

Order

Function

return

Figure

1

init(3, {7, 4, 2}, {25, 5, 40})

 

 

2

add(3, 5, 4)

10

 

3

add(9, 5, 7)

30

 

4

add(1, 15, 4)

25

 

5

add(8, 10, 1)

25

Fig. 1

6

distribute(100)

35

 

7

add(6, 20, 4)

55

Fig. 2

8

distribute(109)

39

 

9

add(5, 20, 9)

25

Fig. 3

10

distribute(131)

45

 

11

remove(1)

25

Fig. 4

12

distribute(110)

40

 

#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;
}
You are required to write a program that manages soldiers.


Each solider has an identification number, team, and reputation score.


The program must have the following features:

  1. Recruit soldiers
  2. Fire soldiers
  3. Change the reputation scores of soldiers
  4. Change all the reputation scores of soldiers in a particular team
  5. Search for a solider with the highest reputation score within a particular team




Implement each required function by referring to the following API description.


※ The function signature below is based on C/C++. As for Java, refer to the provided Solution.java and UserSolution.java.


 


The following is the description of API to be written in the User Code.


void init()

This function is called in each test case.

There are no recruited soldiers in the beginning of the test case.

void hire(int mID, int mTeam, int mScore)

This function recruits a solider whose identification number is mID, team is mTeam, and reputation score is mScore.

It is guaranteed that one solider can only be recruited once in a test case.

 

Parameters

mID : Identification number (1 ≤ mID ≤ 100,000)

mTeam : Team of the soldier (1 ≤ mTeam ≤ 5)

mScore : Reputation score (1 ≤ mScore ≤ 5)

void fire(int mID)

This function fires a solider whose identification number is mID.

It is guaranteed that mID has been recruited when fire() is called.

 

Parameters

mID : Identification number (1 ≤ mID ≤ 100,000)

void updateSoldier(int mID, int mScore)

This function changes the reputation score of mID to mScore.

It is guaranteed that mID has been recruited when this function is called.

 

Parameters

mID : Identification number (1 ≤ mID ≤ 100,000)

mScore : Reputation score (1 ≤ mScore ≤ 5)

void updateTeam(int mTeam, int mChangeScore)

This function changes all the reputation scores of soldiers in a team named mTeam.

It is guaranteed that there are one or more recruited soldiers in mTeam.

 

Scores are changed by updateTeam() according to the following rules:

If ‘the score before change + mChangeScore’ is larger than 5, change the score to 5.

If ‘the score before change + mChangeScore’ is less than 1, change the score to 1.

In other cases, change the score to ‘the score before change + mChangeScore.’

 

Parameters

mTeam : Name of the team (1 ≤ mTeam ≤ 5)

mChangeScore : Reputation score to be added (-4 ≤ mChangeScore ≤ 4)

int bestSoldier(int mTeam)

This function returns the identification number of a soldier with the highest reputation score among the ones in mTeam.

If more than one soldier has the highest score, return the largest identification number.

It is guaranteed that there are one or more recruited soldiers in mTeam.

 

Parameters

mTeam : Name of the team (1 ≤ mTeam ≤ 5)

 

Returns

Identification number of the solider with the highest reputation score


 


[Example]


[a, b, c] in the below table respectively represent the identification number, team, and reputation score of a solider.


Order

Function

Status

Return

1

init()

 

 

2

hire(16, 1, 5)

[16, 1, 5]

 

3

hire(21, 1, 5)

[16, 1, 5], [21, 1, 5]

 

4

bestSoldier(1)

[16, 1, 5], [21, 1, 5]

21

5

fire(21)

[16, 1, 5]

 

6

bestSoldier(1)

[16, 1, 5]

16

7

hire(25, 1, 4)

[16, 1, 5], [25, 1, 4]

 

8

hire(30, 1, 2)

[16, 1, 5], [25, 1, 4], [30, 1, 2]

 

9

updateTeam(1, 1)

[16, 1, 5], [25, 1, 5], [30, 1, 3]

 

10

bestSoldier(1)

[16, 1, 5], [25, 1, 5], [30, 1, 3]

25

11

updateTeam(1, 2)

[16, 1, 5], [25, 1, 5], [30, 1, 5]

 

12

bestSoldier(1)

[16, 1, 5], [25, 1, 5], [30, 1, 5]

30

13

updateSoldier(30, 2)

[16, 1, 5], [25, 1, 5], [30, 1, 2]

 

14

bestSoldier(1)

[16, 1, 5], [25, 1, 5], [30, 1, 2]

25

15

updateTeam(1, -4)

[16, 1, 1], [25, 1, 1], [30, 1, 1]

 

16

hire(1, 1, 3)

[16, 1, 1], [25, 1, 1], [30, 1, 1], [1, 1, 3]

 

17

updateTeam(1, -1)

[16, 1, 1], [25, 1, 1], [30, 1, 1], [1, 1, 2]

 

18

bestSoldier(1)

[16, 1, 1], [25, 1, 1], [30, 1, 1], [1, 1, 2]

1

19

hire(100000, 5, 1)

[16, 1, 1], [25, 1, 1], [30, 1, 1], [1, 1, 2]

[100000, 5, 1]

 

20

bestSoldier(5)

[16, 1, 1], [25, 1, 1], [30, 1, 1], [1, 1, 2]

[100000, 5, 1]

100000


 


[Constraints]


1. init() is called in the beginning of each test case.


2. For each test case, hire() can be called less or equal to 100,000 times.


3. For each test case, fire() can be called less or equal to 100,000 times.


4. For each test case, updateSoldier() can be called less or equal to 100,000 times.


5. For each test case, updateTeam() can be called less or equal to 100,000 times.


6. For each test case, bestSoldier() can be called less or equal to 100 times.
/*
 
* @ file: [E][H2118] Soldier Management
 
* @brief: sample answer
 
* @copyright: All rights reserved (c) 2021 Samsung Electronics, Inc.
 
*/
 
const int MIN_ID = 1;
const int MAX_ID = 100000;
const int MIN_TEAM = 1;
const int MAX_TEAM = 5;
const int MIN_SCORE = 1;
const int MAX_SCORE = 5;
 
struct Node
{
    int id;
    int team;
    Node *prev;
    Node *next;
} soldier[MAX_ID + 1];
 
struct List
{
    Node head;
    Node tail;
 
    static void link(Node *front, Node *back)
    {
        front->next = back;
        back->prev = front;
    }
 
    static void erase(Node *node)
    {
        link(node->prev, node->next);
    }
 
    void initialize()
    {
        link(&head, &tail);
    }
 
    void insert(Node *node)
    {
        link(tail.prev, node);
        link(node, &tail);
    }
 
    bool isEmpty()
    {
        return (head.next == &tail);
    }
 
    void splice(List *list)
    {
        if (list->isEmpty())
            return;
        link(tail.prev, list->head.next);
        link(list->tail.prev, &tail);
        list->initialize();
    }
} soldierGroup[MAX_TEAM + 1][MAX_SCORE + 1];
 
void init()
{
    for (int i = MIN_TEAM; i <= MAX_TEAM; i++)
        for (int j = MIN_SCORE; j <= MAX_SCORE; j++)
            soldierGroup[i][j].initialize();
}
 
void hire(int mID, int mTeam, int mScore)
{
    soldier[mID].id = mID;
    soldier[mID].team = mTeam;
    soldierGroup[mTeam][mScore].insert(soldier + mID);
}
 
void fire(int mID)
{
    List::erase(soldier + mID);
}
 
void updateSoldier(int mID, int mScore)
{
    List::erase(soldier + mID);
    soldierGroup[soldier[mID].team][mScore].insert(soldier + mID);
}
 
void updateTeam(int mTeam, int mChangeScore)
{
    if (mChangeScore > 0)
    {
        for (int i = MAX_SCORE - 1; i >= MIN_SCORE; i--)
        {
            int newScore = i + mChangeScore;
            if (newScore > MAX_SCORE)
                newScore = MAX_SCORE;
            soldierGroup[mTeam][newScore].splice(&soldierGroup[mTeam][i]);
        }
    }
    else if (mChangeScore < 0)
    {
        for (int i = MIN_SCORE + 1; i <= MAX_SCORE; i++)
        {
            int newScore = i + mChangeScore;
            if (newScore < MIN_SCORE)
                newScore = MIN_SCORE;
            soldierGroup[mTeam][newScore].splice(&soldierGroup[mTeam][i]);
        }
    }
}
 
int bestSoldier(int mTeam)
{
    List *maxScoreGroup;
    for (int i = MAX_SCORE; i >= MIN_SCORE; i--)
    {
        if (!soldierGroup[mTeam][i].isEmpty())
        {
            maxScoreGroup = &soldierGroup[mTeam][i];
            break;
        }
    }
 
    int maxId = MIN_ID - 1;
    Node *maxScoreSoldier = maxScoreGroup->head.next;
    while (maxScoreSoldier != &(maxScoreGroup->tail))
    {
        if (maxId < maxScoreSoldier->id)
            maxId = maxScoreSoldier->id;
        maxScoreSoldier = maxScoreSoldier->next;
    }
    return maxId;
}