Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
4.6 kB
1
Indexable
Never
#define HASH_SIZE 105001
#define NEWS_SIZE 50001
#define USER_SIZE 100001
#define SWAP(X, Y) if(X != Y) (X) ^= (Y) ^= (X) ^= (Y)
 
struct NewsData {
    int score;
    int section;
    int call_count;
    bool isErased;
};
 
struct News {
    int id;
    int score;
};
 
struct Heap {
    News news[HASH_SIZE];
    int size;
public:
    bool compare(int first, int second) {
        if(news[first].score > news[second].score 
                || (news[first].score == news[second].score && news[first].id > news[second].id)) {
                    return true;
        }
        return false;
    }
    void push(int id, int score) {
        news[size].id = id;
        news[size].score = score;
        int child = size;
        int parent = (child - 1) / 2;
        while(parent >= 0) {
            if(compare(child, parent)) {
                SWAP(news[child].id, news[parent].id);
                SWAP(news[child].score, news[parent].score);
                child = parent;
                parent = (child - 1) / 2;
            } else break;
        }
        size++;
    }
    News pop() {
        News result;
        result.id = 0;
        if(size == 0) return result;
        result = news[0];
        news[0] = news[--size];
        int parent = 0;
        int left = 2 * parent + 1;
        int right = left + 1;
        int replace = -1;
        while(left <= size) {
            if(right <= size) {
                if(compare(left, right)) {
                    if(compare(left, parent)) {
                        replace = left;
                    }
                } else {
                    if(compare(right, parent)) {
                        replace = right;
                    }
                }
            } else {
                if(compare(left, parent)) {
                    replace = left;
                }
            }
            if(replace != -1) {
                SWAP(news[replace].id, news[parent].id);
                SWAP(news[replace].score, news[parent].score);
                parent = replace;
                left = 2 * parent + 1;
                right = left + 1;
                replace = -1;
            } else break;
        }
        return result;
    }
};
 
NewsData news_data[NEWS_SIZE];
int user_data[USER_SIZE];
int call_number = 0;
Heap heap[11];
 
void init()
{
    for(int i = 0 ; i < 11; i++) {
        heap[i].size = 0;
    }
    for(int i = 0; i < USER_SIZE; i++) {
        user_data[i] = 10;
    }
}
 
void addNews(int mSection, int mNewsId)
{
    int score;
    for(int i = 0; i < 11; i++) {
        score = (mSection == i ) ? 10 : 0;
        heap[i].push(mNewsId, score);
    }
    news_data[mNewsId].section = mSection;
    news_data[mNewsId].score = 0;
    news_data[mNewsId].call_count = 0;
    news_data[mNewsId].isErased = false;
}
 
void eraseNews(int mNewsId)
{
    news_data[mNewsId].isErased = true;
}
 
void readNews(int mUserId, int mNewsId)
{
    news_data[mNewsId].score++;
    int score; 
    for(int i = 0; i < 11; i++) {
        score = (news_data[mNewsId].section == i) ? (news_data[mNewsId].score + 10) : news_data[mNewsId].score;
        heap[i].push(mNewsId, score);
    }
    user_data[mUserId] = news_data[mNewsId].section;
}
 
void changeSection(int mNewsId, int mSection)
{
    int old_section = news_data[mNewsId].section;
    heap[old_section].push(mNewsId, news_data[mNewsId].score);
    heap[mSection].push(mNewsId, news_data[mNewsId].score + 10);
    news_data[mNewsId].section = mSection;
}
 
int getList(int mUserId, int mList[])
{
    call_number++;
    int result = 0, news_id, score;;
    int section = user_data[mUserId];
    while(result < 10) {
        News news = heap[section].pop();
        if(news.id == 0) break;
        news_id = news.id;
        score = news.score;
        if(!news_data[news_id].isErased 
            && news_data[news_id].call_count < call_number
            && ((news_data[news_id].section != section && news_data[news_id].score == score) 
            || (news_data[news_id].section == section && news_data[news_id].score == score - 10))) {
                mList[result++] = news_id;
                news_data[news_id].call_count = call_number;
        }
    }
 
    for(int i = 0; i < result; i++) {
        news_id = mList[i];
        score = (news_data[news_id].section == section) ? news_data[news_id].score + 10 : news_data[news_id].score;
        heap[section].push(news_id, score);
    }
 
    return result;
}