Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
3.9 kB
4
Indexable
Never
#define MAX_USER 1001
#define MAX_POST 100001

struct Post {
	int id;
	int like;
	int timestamp;
	Post* next;
} post[MAX_POST];

struct User {
	int followCount;
	int followUser[MAX_USER];
	Post* headPost;
}user[MAX_USER];

void init(int N)
{
	for (int i = 1; i <= N; i++) {
		user[i].followCount = 1;
		user[i].followUser[0] = i;
		user[i].headPost = nullptr;
	}
}

void follow(int uID1, int uID2, int timestamp)
{
	user[uID1].followUser[user[uID1].followCount] = uID2;
	user[uID1].followCount++;
}

void makePost(int uID, int pID, int timestamp)
{
	post[pID].id = pID;
	post[pID].like = 0;
	post[pID].timestamp = timestamp;
	post[pID].next = user[uID].headPost;
	user[uID].headPost = &post[pID];
}

void like(int pID, int timestamp)
{
	post[pID].like++;
}

int cmpPost(int pID1, int pID2)
{
	if (post[pID1].like != post[pID2].like) {
		return post[pID1].like - post[pID2].like;
	}
	return post[pID1].timestamp - post[pID2].timestamp;
}

void getFeed(int uID, int timestamp, int pIDList[])
{
    int i, j, idx, pos;
    int selectCount1 = 0;
    int selectCount2 = 0;
    int postRank[10];
    struct Post* post1000[1000];
    struct Post* ptr;

    //xet truong hop cac post duoc dang truoc 1000s
    //xet theo nguoi follow
    for (i = 0; i < user[uID].followCount; i++)
    {
        idx = user[uID].followUser[i];  //nguoi follow
        ptr = user[idx].headPost;       //bai dang moi nhat
        post1000[i] = 0;
        while (ptr != 0)
        {
            if (timestamp - ptr->timestamp <= 1000)
            {
                if (selectCount1 < 10)
                {
                    selectCount1++;
                }
                else
                {
                    if (cmpPost(postRank[selectCount1 - 1], ptr->id) > 0)
                    {
                        ptr = ptr->next;
                        continue;
                    }
                }

                for (j = selectCount1 - 2; j >= 0; j--)
                {
                    if (cmpPost(postRank[j], ptr->id) > 0)
                    {
                        break;
                    }
                }
                pos = j + 1;

                for (j = selectCount1 - 2; j >= pos; j--)
                {
                    postRank[j + 1] = postRank[j];
                }
                postRank[pos] = ptr->id;
            }
            else
            {
                post1000[i] = ptr;
                break;
            }
            ptr = ptr->next;
        }
    }

    for (i = 0; i < selectCount1; i++)
    {
        pIDList[i] = postRank[i];
    }

    //xet cac truong hop con lai
    if (selectCount1 < 10)
    {
        int postRank2NeedCount = 10 - selectCount1;
        for (i = 0; i < user[uID].followCount; i++)
        {
            ptr = post1000[i];
            while (ptr != 0)
            {
                if (selectCount2 < postRank2NeedCount)
                {
                    selectCount2++;
                }
                else
                {
                    if (ptr->id < postRank[selectCount2 - 1])
                    {
                        break;
                    }
                }

                for (j = selectCount2 - 2; j >= 0; j--)
                {
                    if (postRank[j] > ptr->id)
                    {
                        break;
                    }
                }
                pos = j + 1;

                for (j = selectCount2 - 2; j >= pos; j--)
                {
                    postRank[j + 1] = postRank[j];
                }
                postRank[pos] = ptr->id;
                ptr = ptr->next;
            }
        }

        for (i = 0; i < selectCount2; i++)
        {
            pIDList[i + selectCount1] = postRank[i];
        }
    }
}