Untitled

/*
 
 
* @ file: [E][H2121] Amusement Park
 
 
* @brief: sample answer
 
 
* @copyright: All rights reserved (c) 2021 Samsung Electronics, Inc.
 
 
*/
 
 
#define NULL 0
#define MAX_RIDE 100
#define MAX_HASH_SIZE 200
#define MAX_PEOPLE_SIZE 10000
 
 
struct People {
    int num;
    int priority;
};
 
 
struct Ride {
    int idx;
    int id;
    int duration;
    int capacity;
    int people;
    int time;
};
 
 
People PeoplePool[MAX_PEOPLE_SIZE];
int PeoplePoolCnt;
Ride RidePool[MAX_RIDE];
Ride* RideArr[MAX_RIDE];
int RideCnt;
 
 
struct HashId {
    int key;
    Ride* data;
};
HashId HashIdTbl[MAX_HASH_SIZE];
 
 
Ride* findId(int key) {
    unsigned long h = key % MAX_HASH_SIZE;
    int cnt = MAX_HASH_SIZE;
 
 
    while (HashIdTbl[h].key != -1 && cnt--) {
        if (HashIdTbl[h].key == key) {
            return HashIdTbl[h].data;
        }
        h = (h + 1) % MAX_HASH_SIZE;
    }
    return NULL;
}
 
 
void addId(int key, Ride* data) {
    unsigned long h = key % MAX_HASH_SIZE;
 
 
    while (HashIdTbl[h].key != -1) {
        h = (h + 1) % MAX_HASH_SIZE;
    }
 
 
    HashIdTbl[h].key = key;
    HashIdTbl[h].data = data;
}
 
 
People* Heap[MAX_RIDE][MAX_PEOPLE_SIZE];
int HeapSize[MAX_RIDE];
 
 
void heapPush(int rideIdx, People* value) {
    Heap[rideIdx][HeapSize[rideIdx]] = value;
 
 
    int current = HeapSize[rideIdx];
    while (current > 0 && Heap[rideIdx][current]->priority > Heap[rideIdx][(current - 1) / 2]->priority) {
        People* temp = Heap[rideIdx][(current - 1) / 2];
        Heap[rideIdx][(current - 1) / 2] = Heap[rideIdx][current];
        Heap[rideIdx][current] = temp;
        current = (current - 1) / 2;
    }
 
 
    HeapSize[rideIdx]++;
}
 
 
People* heapPop(int rideIdx) {
    if (HeapSize[rideIdx] <= 0) {
        return NULL;
    }
 
 
    People* ret = Heap[rideIdx][0];
    HeapSize[rideIdx]--;
 
 
    Heap[rideIdx][0] = Heap[rideIdx][HeapSize[rideIdx]];
 
 
    int current = 0;
    while (current * 2 + 1 < HeapSize[rideIdx]) {
        int child;
        if (current * 2 + 2 == HeapSize[rideIdx]) {
            child = current * 2 + 1;
        }
        else {
            child = Heap[rideIdx][current * 2 + 1]->priority > Heap[rideIdx][current * 2 + 2]->priority ? current * 2 + 1 : current * 2 + 2;
        }
 
 
        if (Heap[rideIdx][current]->priority > Heap[rideIdx][child]->priority)
            break;
 
 
        People* temp = Heap[rideIdx][current];
        Heap[rideIdx][current] = Heap[rideIdx][child];
        Heap[rideIdx][child] = temp;
 
 
        current = child;
    }
    return ret;
}
 
 
People* newPeople(int priority, int num) {
    People* ret = &PeoplePool[PeoplePoolCnt++];
    ret->priority = priority;
    ret->num = num;
    return ret;
}
 
 
void process(Ride* ride, int tStamp) {
    while (ride->time <= tStamp && HeapSize[ride->idx] > 0) {
        int remainder = ride->capacity;
        while (remainder > 0 && HeapSize[ride->idx] > 0) {
            People* curr = Heap[ride->idx][0];
            if (remainder < curr->num) {
                curr->num -= remainder;
                ride->people -= remainder;
                break;
            }
 
 
            remainder -= curr->num;
            ride->people -= curr->num;
            heapPop(ride->idx);
        }
        ride->time += ride->duration;
    }
}
 
 
////////////////////////////////////////////////
 
 
void init(int N, int mId[], int mDuration[], int mCapacity[]) {
    RideCnt = PeoplePoolCnt = 0;
    for (int i = 0; i < MAX_HASH_SIZE; ++i) {
        HashIdTbl[i].key = -1;
    }
 
 
    for (int i = 0; i < MAX_RIDE; ++i) {
        HeapSize[i] = 0;
    }
 
 
    for (int i = 0; i < N; ++i) {
        Ride* ride = &RidePool[RideCnt++];
        addId(mId[i], ride);
        ride->idx = i;
        ride->id = mId[i];
        ride->duration = mDuration[i];
        ride->capacity = mCapacity[i];
        ride->people = ride->time = 0;
        RideArr[i] = ride;
    }
}
 
 
int add(int tStamp, int mId, int mNum, int mPriority) {
    Ride* ride = findId(mId);
    process(ride, tStamp - 1);
    if (ride->time < tStamp) {
        ride->time = tStamp;
    }
 
 
    ride->people += mNum;
    heapPush(ride->idx, newPeople(mPriority, mNum));
    process(ride, tStamp);
 
 
    if (!HeapSize[ride->idx])
        return 0;
    return Heap[ride->idx][0]->priority;
}
 
 
void search(int tStamp, int mCount, int mId[], int mWait[]) {
    for (int i = 0; i < RideCnt; ++i) {
        process(&RidePool[i], tStamp);
    }
 
 
    for (int i = 0; i < mCount; ++i) {
        for (int j = i + 1; j < RideCnt; ++j) {
            if (RideArr[i]->people < RideArr[j]->people
             || (RideArr[i]->people == RideArr[j]->people && RideArr[i]->id < RideArr[j]->id)) {
                Ride* tmp = RideArr[i];
                RideArr[i] = RideArr[j];
                RideArr[j] = tmp;
            }
        }
        mId[i] = RideArr[i]->id;
        mWait[i] = RideArr[i]->people;
    }
}