Untitled
unknown
plain_text
a year ago
7.2 kB
12
Indexable
[Problem Description]
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
[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.
[Input and Output]
As the input and output are processed in the provided code in the Main, they are not processed separately in the User Code.
The output result for the sample input is in the format of “#TC number result.” It is the correct answer if the result is 100; it is the wrong answer if it is 0.
==============================================================
#include<iostream>
using namespace std;
#define MAXN 100005
struct ListNode {
int id;
int team;
int score;
ListNode* prev;
ListNode* next;
ListNode() {
id = -1;
team = -1;
score = -1;
prev = nullptr;
next = nullptr;
}
ListNode(int i, int t, int s) {
id = i;
team = t;
score = s;
prev = nullptr;
next = nullptr;
}
};
ListNode* map[MAXN];
class DLL {
public:
ListNode *head = new ListNode();
ListNode *tail = new ListNode();
DLL() {
head->next = tail;
tail->prev = head;
}
void insert(ListNode* node) {
ListNode *temp = head->next;
head->next = node;
node->prev = head;
node->next = temp;
temp->prev = node;
}
void remove(ListNode* node) {
ListNode * left = node->prev;
ListNode * right = node->next;
left->next = right;
right->prev = left;
delete(node);
}
void clear() {
if (isEmpty()) return;
head->next = tail;
tail->prev = head;
}
bool isEmpty() {
return head->next == tail;
}
void merge(DLL someList) {
ListNode *temp = head->next;
head->next = someList.head->next;
someList.head->next->prev = head;
someList.tail->prev->next = temp;
temp->prev = someList.tail->prev;
someList.clear();
}
int getMax() {
ListNode*temp = head->next;
int max = -1;
while (temp != tail) {
if (temp->id > max) max = temp->id;
temp = temp->next;
}
return max;
}
};
DLL* soldiers[6][6];
void init() {
for (int i = 1; i < 6; i++)
for (int j = 1; j < 6; j++) soldiers[i][j] = new DLL();
for (int i = 0; i < MAXN; i++) map[i] = NULL;
}
void hire(int mID, int mTeam, int mScore) {
ListNode *temp = new ListNode(mID, mTeam, mScore);
soldiers[mTeam][mScore]->insert(temp);
map[mID] = temp;
}
void fire(int mID) {
ListNode s = *map[mID];
soldiers[s.team][s.score]->remove(map[mID]);
map[mID] = nullptr;
}
void updateSoldier(int mID, int mScore) {
int t = (*map[mID]).team;
fire(mID);
hire(mID, t, mScore);
}
void updateTeam(int mTeam, int mChangeScore) {
if (mChangeScore == 0) return;
int count[6];
int d;
for (int i = 1; i < 6; i++) {
d = i + mChangeScore;
if (d >= 5) count[i] = 5;
else if (d <= 1) count[i] = 1;
else count[i] = d;
}
if (mChangeScore > 0) {
for (int i = 4; i >= 1; i--) {
soldiers[mTeam][count[i]]->merge(*soldiers[mTeam][i]);
}
}
else {
for (int i = 2; i <= 5; i++) {
soldiers[mTeam][count[i]]->merge(*soldiers[mTeam][i]);
}
}
}
int bestSoldier(int mTeam) {
int best = 0;
for (int i = 5; i > 0; i--) {
if (!soldiers[mTeam][i]->isEmpty()) {
best = soldiers[mTeam][i]->getMax();
break;
}
}
return best;
}Editor is loading...
Leave a Comment