Skip to content

Instantly share code, notes, and snippets.

@idkiller

idkiller/user.cpp

Created June 27, 2019 03:11
Show Gist options
  • Save idkiller/530ff50de8f57bd4ed55c3669780bab0 to your computer and use it in GitHub Desktop.
Save idkiller/530ff50de8f57bd4ed55c3669780bab0 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. idkiller created this gist Jun 27, 2019.
    144 changes: 144 additions & 0 deletions user.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,144 @@
    #define DEBUG

    #ifdef DEBUG
    #include <stdio.h>
    #endif // DEBUG

    template<typename T, bool C(T, T)>
    class PriorityQue {
    public:
    PriorityQue() : PriorityQue(0) {}
    PriorityQue(int n) : size(0), maxSize(n) {
    heap = new T[maxSize];
    }
    ~PriorityQue() {
    printf("destructor!\n");
    delete[] heap;
    }
    void push(T value) {
    if (size + 1 > maxSize) return;
    heap[size] = value;
    unsigned int current = size;
    unsigned int parent = (size - 1) >> 1;

    while (current > 0 && C(heap[current], heap[parent])) {
    swap(heap[current], heap[parent]);
    current = parent;
    parent = (current - 1) >> 1;
    }
    size++;
    }
    T pop() {
    if (size < 1) return nullptr;
    T result = heap[0];
    size--;

    heap[0] = heap[size];
    unsigned int current = 0;
    unsigned int left = (current << 1) + 1;
    unsigned int right = (current << 1) + 2;
    unsigned int max = current;

    while (left < size) {
    if (!C(heap[size], heap[left])) {
    max = left;
    }
    if (right < size && !C(heap[max], heap[right])) {
    max = right;
    }
    if (max == current) {
    break;
    }
    else {
    swap(heap[current], heap[max]);
    current = max;
    left = (current << 1) + 1;
    right = (current << 1) + 2;
    }
    }

    return result;
    }

    T first() {
    return size > 0 ? heap[0] : nullptr;
    }
    private:
    T* heap = nullptr;
    unsigned int size;
    unsigned int maxSize;
    void swap(T &a, T &b) {
    T tmp = a;
    a = b;
    b = tmp;
    }
    };

    struct STUDENT {
    int id;
    int score;
    };

    static int count;
    static STUDENT datas[50000];

    bool comp_asc(STUDENT* a, STUDENT* b) {
    //return a->score == b->score ? a->id > b->id : a->score > b->score;
    return a->score >= b->score;
    }
    bool comp_desc(STUDENT* a, STUDENT* b) {
    //return a->score == b->score ? a->id < b->id : a->score < b->score;
    return a->score <= b->score;
    }


    static PriorityQue<STUDENT*, comp_asc> max_que;
    static PriorityQue<STUDENT*, comp_desc> min_que;
    static PriorityQue<STUDENT*, comp_desc> mid_high_que;
    static PriorityQue<STUDENT*, comp_desc> mid_low_que;

    void init(int N, STUDENT students[]) {
    count = N;

    max_que = PriorityQue<STUDENT*, comp_asc>(count);
    min_que = PriorityQue<STUDENT*, comp_desc>(count);
    mid_high_que = PriorityQue<STUDENT*, comp_desc>(count);
    mid_low_que = PriorityQue<STUDENT*, comp_desc>(count);


    for (int i = 0; i < count; i++) {
    datas[i] = students[i];

    max_que.push(&datas[i]);
    min_que.push(&datas[i]);
    STUDENT *mh = mid_high_que.first();
    if (mh != nullptr && comp_asc(&datas[i], mh)) {
    mid_low_que.push(mid_high_que.pop());
    }
    mid_high_que.push(&datas[i]);

    #ifdef DEBUG
    printf("[%d: %d] ", datas[i].id, datas[i].score);
    #endif // DEBUG
    }
    #ifdef DEBUG
    printf("\n");
    #endif // DEBUG

    #ifdef DEBUG
    printf("max => %d: %d\n", max_que.first()->id, max_que.first()->score);
    printf("min => %d: %d\n", min_que.first()->id, min_que.first()->score);
    printf("mid high => %d: %d\n", mid_high_que.first()->id, mid_high_que.first()->score);
    printf("mid low => %d: %d\n", mid_low_que.first()->id, mid_low_que.first()->score);
    #endif
    }

    void addStudent(STUDENT student) {
    }

    int removeStudents(int K) {
    return 0;
    }

    void getSum(int sum[]) {
    }