Untitled
unknown
plain_text
a year ago
2.5 kB
3
Indexable
Never
#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; }