Untitled

mail@pastecode.io avatar
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;
}