Untitled
unknown
plain_text
a year ago
17 kB
3
Indexable
[Problem Description]
There is a system managing school records.
When adding a school record, the student’s grade, gender, and score are given with his/her ID.
When deleting a school record, only the ID of the student is given.
For school record inquiry, return the ID of the student with the lowest score among students with at least a certain score
while meeting the conditions of grade (Grades 1 to 3) and gender (male/female).
For instance, given the conditions of grade {Grade 1, Grade 3}, gender {female}, and score 80,
among female students in Grades 1 and 3 whose scores are greater than or equal to 80, return the ID of the student with the lowest score.
Given the conditions of grade {Grade 2}, gender {male, female}, and score 90,
among male and female students in Grade 2 whose scores are greater than or equal to 90, return the ID of the student with the lowest score.
You are required to implement a system managing school records that operates as mentioned above.
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()
This function is called in the beginning of each test case.
The system will have no registered school records.
int add(int mId, int mGrade, char mGender[7], int mScore)
This function adds mScore, the score of the student whose ID, grade, and gender are mId, mGrade, and mGender, respectively.
In the case of gender, “male” is for men and “female” is for women. It is a string that ends with ‘＼0’.
This function returns the ID of the student whose score is the highest among students in mGrade whose genders are mGender.
If there are multiple students with the highest score, return the ID with the biggest value.
The ID of the student whose score is already recorded in the system is not given as an input. However, it can be added again after the record is deleted.
Parameters
mId: The ID of student ( 1 ≤ mId ≤ 1,000,000,000 )
mGrade: The grade of student ( 1 ≤ mGrade ≤ 3 )
mGender: The gender of student ( A string of “male” or “female” that ends with ‘＼0’ )
mScore: The score of student ( 0 ≤ mScore ≤ 300,000 )
Returns
Return the ID of the student with the highest score among students in mGrade whose genders are mGender.
int remove(int mId)
This function deletes the record of the student whose ID is mId.
If the score of student mId is not recorded in the system, this function returns 0.
After the deletion, this function returns the ID of the student whose score is the lowest among students of the same gender and in the same grade with student mId.
If there are multiple students with the lowest score, return the ID with the smallest value.
After the deletion, return 0 when there are NO students of the same gender in the same grade.
Parameters
mId: The ID of student ( 1 ≤ mId ≤ 1,000,000,000 )
Returns
After the deletion, return the ID of the student whose score is the lowest among students of the same gender and in the same grade with student mId.
If there is NO student mId, or if there are NO students of the same gender in the same grade with student mId, return 0.
int query(int mGradeCnt, int mGrade[], int mGenderCnt, char mGender[][7], int mScore)
This function returns the ID of the student with the lowest score among students within the sets of grade, mGrade, and gender, mGender, whose scores are greater than or equal to mScore.
If there are multiple students with the lowest score, this function returns the ID with the smallest value.
The number of grades, mGradeCnt, is given as mGrade array. For instance, Grades 1 and 3 are given as {1, 3}.
The number of genders, mGenderCnt, is given as mGender array. For instance, men is given as {“male”} while men and women are given as {“male”, “female”}.
If there is NO student whose score is greater than or equal to mScore, this function returns 0.
Parameters
mGradeCnt: The number of elements in mGrade array ( 1 ≤ mGradeCnt ≤ 3 )
mGrade: The array of grade ( 1 ≤ mGrade[i] ≤ 3 )
mGenderCnt: The number of elements in mGender array ( 1 ≤ mGenderCnt ≤ 2 )
mGender: The array of gender ( mGender[i] = A string of “male” or “female” that ends with ‘＼0’ )
mScore: The score of student ( 0 ≤ mScore ≤ 300,000 )
Returns
Return the ID of the student with the lowest score among students within the sets of mGrade and mGender whose scores are greater than or equal to mScore.
If there is NO student whose score is greater than or equal to mScore, return 0.
[Example]
Let’s look into a case where functions are called as in [Table 1] below..
Order
Function
return
Figure
1
init()
2
add(500, 1, male, 1250)
500
3
add(400, 3, female, 2900)
400
4
add(900, 2, female, 2500)
900
5
add(700, 2, male, 2500)
700
6
add(600, 1, female, 1750)
600
7
add(800, 3, male, 1000)
800
Fig. 1
8
add(300, 2, female, 2000)
900
Fig. 2
9
query(2, {2, 3}, 2, {male, female}, 2500)
700
Fig. 3
10
query(3, {1, 2, 3}, 1, {male}, 1100)
500
Fig. 4
11
add(100, 2, female, 2500)
900
Fig. 5
12
query(1, {2}, 2, {male, female}, 2200)
100
Fig. 6
13
remove(300)
100
Fig. 7
14
remove(200)
0
15
add(300, 3, female, 3000)
300
Fig. 8
16
query(2, {1, 3}, 1, {female}, 1800)
400
Fig. 9
17
remove(800)
0
Fig. 10
18
query(3, {1, 2, 3}, 2, {male, female}, 1000)
500
Fig. 11
[Table 1]
(Order 1) In the beginning, there are NO school records registered.
(Order 2) Add 1250, the score of a male student in Grade 1 whose ID is 500.
When it comes to male students in Grade 1, there is only the student whose ID is 500. Thus, return 500 for the student ID with the highest score.
(Order 3) Add 2900, the score of a female student in Grade 3 whose ID is 400.
When it comes to female students in Grade 3, there is only the student whose ID is 400. Thus, return 400 for the student ID with the highest score.
(Order 4) Add 2500, the score of a female student in Grade 2 whose ID is 900.
When it comes to female students in Grade 2, there is only the student whose ID is 900. Thus, return 900 for the student ID with the highest score.
(Order 5) Add 2500, the score of a male student in Grade 2 whose ID is 700.
When it comes to male students in Grade 2, there is only the student whose ID is 700. Thus, return 700 for the student ID with the highest score.
(Order 6) Add 1750, the score of a female student in Grade 1 whose ID is 600.
When it comes to female students in Grade 1, there is only the student whose ID is 600. Thus, return 600 for the student ID with the highest score.
(Order 7) Add 1000, the score of a male student in Grade 3 whose ID is 800.
When it comes to male students in Grade 3, there is only the student whose ID is 800. Thus, return 800 for the student ID with the highest score.
[Fig. 1] shows the result of the function call.
[Fig. 1]
(Order 8) Add 2000, the score of a female student in Grade 2 whose ID is 300.
Among female students in Grade 2, return 900 for the ID of the student with the highest score. [Fig. 2] shows the result of the function call.
[Fig. 2]
(Order 9) Students who are within the sets of {Grade 2, Grade 3} and {male, female} are students in the box colored yellow as in [Fig. 3].
Among them, students whose scores are greater than or equal to 2500 are colored blue.
Among the students with blue font color, there are two students whose scores are the lowest, ID 700 and ID 900. Thus return 700, the ID whose value is smaller.
[Fig. 3]
(Order 10) Students who are within the sets of {Grade 1, Grade 2, Grade 3} and {male} are students in the box colored yellow as in [Fig. 4].
Among them, students whose scores are greater than or equal to 1100 are colored blue.
Among the students with blue font color, return 500 for the ID of the student with the lowest score.
[Fig. 4]
(Order 11) Add 2500, the score of a female student in Grade 2 whose ID is 100.
Among female students in Grade 2, there are two students with the highest score, ID 100 and ID 900. Thus, return 900, the ID whose value is bigger.
[Fig. 5] shows the result of the function call.
[Fig. 5]
(Order 12) Students who are within the sets of {Grade 2} and {male, female} are students in the box colored yellow as in [Fig. 6].
Among them, students whose scores are greater than or equal to 2200 are colored blue.
Among the students with blue font color, there are three students with the lowest score, ID 700, ID 100, and ID 900. Thus, return 100, the ID with the lowest value.
[Fig. 6]
(Order 13) Delete the record of the student whose ID is 300.
After the deletion, among students who are of the same gender and in the same grade with the student whose ID is 300, there are two students with the lowest score, ID 100 and ID 900.
Between the two, return 100, the ID whose value is smaller. [Fig. 7] shows the result of the function call.
[Fig. 7]
(Order 14) Delete the record of the student whose ID is 200. As there is NO record of a student whose ID is 200 in the system, the deletion fails. Thus, return 0.
(Order 15) Add 3000, the score of a female student in Grade 3 whose ID is 300.
Among female students in Grade 3, return 300, the ID of the student with the highest score. [Fig. 8] shows the result of the function call.
[Fig. 8]
(Order 16) Students who are within the sets of {Grade 1, Grade 3} and {female} are students in the box colored yellow as in [Fig. 9].
Among them, students whose scores are greater than or equal to 1800 are colored blue.
Among the students with blue font color, return 400 for the ID of the student with the lowest score.
[Fig. 9]
(Order 17) Delete the record of the student whose ID is 800.
After the deletion, as there are NO students who are of the same gender and in the same grade with the student whose ID is 800, return 0.
[Fig. 10] shows the result of the function call.
[Fig. 10]
(Order 18) Students who are within the sets of {Grade 1, Grade 2, Grade 3} and {male, female} are students in the box colored yellow as in [Fig. 11].
Among them, students whose scores are greater than or equal to 1000 are colored blue.
Among the students with blue font color, return 500 for the ID of the student with the lowest score.
[Fig. 11]
[Constraints]
1. init() is called in the beginning of each test case.
2. For each test case, the total sum of add() function call is less than or equal to 20,000.
3. For each test case, the sum of calls of the all functions is less than or equal to 80,000.
[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.
#define _for(i,a,b) for(int i=(a);i<(b);i++ )
#define NULL 0
#define MAXN 20001
#define MAXH 13333
#define male 1
#define female 2
#define MAXL 500
#define MAXC 300001
#define MAXHL (MAXC/MAXL)
struct _node {
int id;
int grade;
int gender;
int score;
_node* hpre;
_node* hnext;
_node* next;
_node* pre;
//_node *pnext;
//_node *ppre;
};
_node NodeN[MAXN];
_node Hash[MAXH];
_node Head[4][3][MAXL + 1];
//_node hhead;
int g_node_cnt;
void init_hashhead() {
_for(i, 0, MAXH) {
Hash[i].hnext = Hash[i].hpre = &(Hash[i]);
}
_for(i, 1, 4) {
_for(j, 1, 3) {
_for(k, 0, MAXL + 1) {
Head[i][j][k].next = Head[i][j][k].pre = &(Head[i][j][k]);
}
}
}
//hhead.pnext = hhead.ppre = &(hhead);
}
void add_node2hash(_node* node) {
int idx = node->id % MAXH;
_node* head = &(Hash[idx]);
node->hnext = head->hnext;
node->hpre = head;
head->hnext->hpre = node;
head->hnext = node;
}
void del_node2hash(_node* node) {
if (node->hnext != NULL)
node->hnext->hpre = node->hpre;
if (node->hpre != NULL)
node->hpre->hnext = node->hnext;
node->hnext = NULL;
node->hpre = NULL;
}
_node* find_node4hash(int id) {
int idx = id % MAXH;
_node* head = &(Hash[idx]);
_node* pre = head->hnext;
while (pre != head) {
if (pre->id == id)
return pre;
pre = pre->hnext;
}
return NULL;
}
void add_node2head(_node* node) {
int idx = node->score / MAXHL;
int grade = node->grade;
int gender = node->gender;
_node* head = &(Head[grade][gender][idx]);
_node* pre = head->next;
while (pre != head && pre != NULL) {
if (pre->score < node->score) {
pre = pre->next;
}
else if (pre->score == node->score) {
if (pre->id > node->id)
break;
pre = pre->next;
}
else
break;
}
if (pre == NULL) {
node->next = head->next;
node->pre = head;
head->next->pre = node;
head->next = node;
}
else {
//前插
node->next = pre;
node->pre = pre->pre;
pre->pre->next = node;
pre->pre = node;
}
}
void del_node4head(_node* node) {
if (node->pre != NULL)
node->pre->next = node->next;
if (node->next != NULL)
node->next->pre = node->pre;
node->next = NULL;
node->pre = NULL;
}
int find_high4head(_node* node) {////相同grade，相同gender，score最大的id最大的node
int idx = MAXL;
int grade = node->grade;
int gender = node->gender;
_node* head = NULL;
_node* pre = NULL;
while (idx >= 0) {
head = &(Head[grade][gender][idx]);
pre = head->pre;
if (pre != head)
return pre->id;
idx--;
}
return 0;
}
int find_low4head(_node* node) {//相同grade，相同gender，score最小的node
int idx = 0;
int grade = node->grade;
int gender = node->gender;
_node* head = NULL;
_node* pre = NULL;
while (idx < MAXL) {
head = &(Head[grade][gender][idx]);
pre = head->next;
if (pre != head)
return pre->id;
idx++;
}
return 0;
}
_node* find_more4head(int grade, int gender, int score) {//返回score大于score的最低分
int idx = score / MAXHL;
_node* head = NULL;
_node* pre = NULL;
while (idx < MAXL) {
head = &(Head[grade][gender][idx]);
pre = head->next;
while (pre != head) {
if (pre->score >= score)
return pre;
pre = pre->next;
}
idx++;
}
return NULL;
}
void init() {
init_hashhead();
g_node_cnt = 0;
return;
}
int get_gender(char str[]) {
if (str[0] == 'm')
return male;
return female;
}
int add(int mId, int mGrade, char mGender[7], int mScore) {
_node* node = &(NodeN[g_node_cnt++]);
node->id = mId;
node->grade = mGrade;
node->gender = get_gender(mGender);
node->score = mScore;
add_node2hash(node);
add_node2head(node);
return find_high4head(node);
}
int remove(int mId) {
_node* node = find_node4hash(mId);
if (node == NULL)
return 0;
else {
int id = 0;
del_node2hash(node);
del_node4head(node);
id = find_low4head(node);
return id;
}
return 0;
}
int query(int mGradeCnt, int mGrade[], int mGenderCnt, char mGender[][7], int mScore) {
//int grade_cn = mGradeCnt;
//int gender_cn = mGenderCnt;
_node* tmp = NULL;
_node* ret = NULL;
int gender = -1;
_for(i, 0, mGradeCnt) {
_for(j, 0, mGenderCnt) {
gender = get_gender(mGender[j]);
tmp = find_more4head(mGrade[i], gender, mScore);
if (tmp != NULL) {
if (ret == NULL)
ret = tmp;
else {
if (ret->score > tmp->score)
ret = tmp;
else if (ret->score == tmp->score) {
if (ret->id > tmp->id)
ret = tmp;
}
}
}
}
}
if (ret == NULL)
return 0;
return ret->id;
}