#include <set>
#define MAX 20021
using namespace std;
struct cmp {
inline bool operator()(const int& idx1, const int& idx2) const {
if (student[idx1].score != student[idx2].score)
return student[idx1].score > student[idx2].score;
return student[idx1].id > student[idx2].id;
}
};
struct Student {
int id;
int grade;
int gender;
int score;
int next;
set<int, cmp>::iterator it;
Student(int mId, int mGrade, int mGender, int mScore) {
id = mId;
grade = mGrade;
gender = mGender;
score = mScore;
next = 0;
}
};
Student student[MAX];
set<int, cmp> mySet[4][2];
int hashTable[MAX];
int index;
void init()
{
index = 1;
for (int i = 1; i < 4; i++)
for (int j = 0; j < 2; j++)
mySet[i][j] = set<int, cmp>();
for (int i = 0; i < MAX; i++)
hashTable[i] = 0;
return;
}
int getIndex(int mId)
{
int key = mId % MAX;
int idx = hashTable[key];
while (1) {
if (student[idx].id == mId)
return idx;
idx = student[idx].next;
}
return 0;
}
int add(int mId, int mGrade, char mGender[7], int mScore)
{
int gender = mGender[0] == 'm' ? 1 : 0;
int key = mId % MAX;
student[index] = Student(mId, mGrade, gender, mScore);
student[index].next = hashTable[key];
student[index].it = mySet[mGrade][gender].insert(index).first; //iterator chi toi phan tu da duoc chen
index++;
int findId = student[*mySet[mGrade][gender].begin()].id;
return findId;
}
int remove(int mId)
{
int idx = getIndex(mId);
if (idx == 0)
return 0;
int gender = student[idx].gender;
int grade = student[idx].grade;
mySet[grade][gender].erase(idx);
int findId;
if (mySet[grade][gender].size() != 0) {
findId = student[*(--mySet[grade][gender].end())].id;
}
return findId;
}
int query(int mGradeCnt, int mGrade[], int mGenderCnt, char mGender[][7], int mScore)
{
student[0].score = mScore;
int minScore = 400000;
int minID = 1000000001;
int gender;
for (int i = 0; i < mGradeCnt; i++) {
for (int j = 0; j < mGenderCnt; j++) {
gender = mGender[j][0] == 'm' ? 1 : 0;
auto it = mySet[mGrade[i]][gender].lower_bound(0); //tra ve iterator cua phan tu dau tien khong nho hon 0
if (it != mySet[mGrade[i]][gender].begin()) {
it--;
if ((student[*it].score < minScore) || ((student[*it].id < minID) && (student[*it].score == minScore))) {
minScore = student[*it].score;
minID = student[*it].id;
}
}
}
}
return 0;
}