Untitled

 avatar
Darin
plain_text
a year ago
4.3 kB
1
Indexable
Never
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
 
using namespace std;
 
class People {
public:
    int ID;
    int jobID;
    int point;
    int section;
    bool status;
    void init(int ID1, int jobID1, int point1, int section1) {
        ID = ID1;
        jobID = jobID1;
        point = point1;
        section = section1;
        status = true;
    }
};
People pool[180000];
int poolCnt;
People *getPeople(int ID1, int jobID1, int point1, int section1) {
    pool[poolCnt].init(ID1, jobID1, point1, section1);
    return &pool[poolCnt++];
}
People *getPeople(People *p) {
    return getPeople(p->ID, p->jobID, p->point, p->section);
}
class CmpMaxHeap {
public:
    bool operator() (const People *p1, const People *p2) const {
        if (p1->point != p2->point) return p2->point > p1->point;
        return p2->ID < p1->ID;
    }
};
class CmpMinHeap {
public:
    bool operator() (const People *p1, const People *p2) const {
        if (p1->point != p2->point) return p2->point < p1->point;
        return p2->ID > p1->ID;
    }
};
class Section {
public:
    priority_queue<People *, vector<People *>, CmpMaxHeap> maxHeap;
    priority_queue<People *, vector<People *>, CmpMinHeap> minHeap;
};
 
int secNumber;
Section listSec[11];
unordered_map<int, People *> hashPeople;
unordered_map<int, vector<People *>> hashJob;
 
void addNewPeople(People *p) {
    hashPeople[p->ID] = p;
    hashJob[p->jobID].push_back(p);
    listSec[p->section].maxHeap.push(p);
    listSec[p->section].minHeap.push(p);
}
 
void init(int N, int M, int J, int mPoint[], int mJobID[]) {
    poolCnt = 0;
    secNumber = N/M;
    hashPeople.clear();
    hashJob.clear();
    for (int i = 0; i < secNumber; i++) {
        listSec[i].maxHeap = priority_queue<People *, vector<People *>, CmpMaxHeap>();
        listSec[i].minHeap = priority_queue<People *, vector<People *>, CmpMinHeap>();
    }
    People *p;
    for (int i = 0; i < N; i++) {
        p = getPeople(i, mJobID[i], mPoint[i], i/M);
        if (hashJob.find(mJobID[i]) == hashJob.end()) {
            hashJob[mJobID[i]] = vector<People *>();
        }
        addNewPeople(p);
    }
}
void destroy() {
}
 
int update(int mID, int mPoint) {
    People *oldPeople = hashPeople[mID];
    oldPeople->status = false;
    People *newPeople = getPeople(oldPeople);
    newPeople->point += mPoint;
    addNewPeople(newPeople);
    return newPeople->point;
}
 
int updateByJob(int mJobID, int mPoint) {
    int sum = 0;
    vector<People *> pByJob = hashJob[mJobID];
    hashJob[mJobID] = vector<People *>();
    People *newPeople;
    for (People *tp : pByJob) {
        if (tp->status == false) continue;
        tp->status = false;
        newPeople = getPeople(tp);
        newPeople->point += mPoint;
        addNewPeople(newPeople);
        sum += newPeople->point;
    }
    return sum;
}
 
int move(int mNum) {
    int sum = 0;
    vector<People *> moveUp[10];
    vector<People *> moveDown[10];
    int cnt;
    People *tp, *newPeople;
    for (int i = 0; i < secNumber - 1; i++) {
        // moveDown mNum People from i to i + 1
        // moveUp mNum People from i + 1 to i
        cnt = 0;
        while (cnt < mNum) {
            tp = listSec[i].minHeap.top();
            listSec[i].minHeap.pop();
            if (tp->status == false) continue;
            tp->status = false;
            cnt++;
            sum += tp->point;
 
            newPeople = getPeople(tp);
            moveDown[i].push_back(newPeople);
        }
        cnt = 0;
        while (cnt < mNum) {
            tp = listSec[i + 1].maxHeap.top();
            listSec[i + 1].maxHeap.pop();
            if (tp->status == false) continue;
            tp->status = false;
            cnt++;
            sum += tp->point;
 
            newPeople = getPeople(tp);
            moveUp[i + 1].push_back(newPeople);
        }
    }
    for (int i = 0; i < secNumber - 1; i++) {
        for (People *p : moveDown[i]) {
            p->section = i + 1;
            addNewPeople(p);
        }
        for (People *p : moveUp[i + 1]) {
            p->section = i;
            addNewPeople(p);
        }
    }
    return sum;
}