#include <iostream>
using namespace std;
#define MAX_N 1001
#define MAX_P 100001
#define SPACE 5
typedef struct _stack {
int id;
int next;
} STACK;
STACK uFollow[MAX_N + SPACE]; // 인덱스 uFollow[]
STACK uFollows[MAX_P + SPACE]; //
STACK uPID[MAX_N + SPACE]; //
STACK uPIDs[MAX_P + SPACE]; //
int pLike[MAX_P + SPACE] = { 0, }; //
int pTimestamp[MAX_P + SPACE] = { 0, };
int followNum = 0;
int pidNum = 0;
int heapSize = 0;
int heap[MAX_P + SPACE];
void pushFollow(int uid1, int uid2) {
uFollows[followNum].id = uid2;
uFollows[followNum].next = uFollow[uid1].next;
uFollow[uid1].next = followNum;
followNum++;
}
void pushPid(int uid, int pid) {
uPIDs[pidNum].id = pid;
uPIDs[pidNum].next = uPID[uid].next;
uPID[uid].next = pidNum;
pidNum++;
}
bool compare(int pid1, int pid2, int timestamp) {
if (timestamp - pTimestamp[pid1] <= 1000 && timestamp - pTimestamp[pid2] <= 1000) {
if (pLike[pid1] != pLike[pid2])
return pLike[pid1] > pLike[pid2];
else
return pTimestamp[pid1] > pTimestamp[pid2];
}
else
return pTimestamp[pid1] > pTimestamp[pid2];
}
void heapInit(void)
{
heapSize = 0;
}
int heapPush(int pid, int timestamp)
{
heap[heapSize] = pid;
int current = heapSize;
while (current > 0 && compare(heap[current], heap[(current - 1) / 2], timestamp))
{
int temp = heap[(current - 1) / 2];
heap[(current - 1) / 2] = heap[current];
heap[current] = temp;
current = (current - 1) / 2;
}
heapSize = heapSize + 1;
return 1;
}
int heapPop(int *pid, int timestamp)
{
*pid = heap[0];
heapSize = heapSize - 1;
heap[0] = heap[heapSize];
int current = 0;
while (current * 2 + 1 < heapSize)
{
int child;
if (current * 2 + 2 == heapSize)
{
child = current * 2 + 1;
}
else
{
child = compare(heap[current * 2 + 1], heap[current * 2 + 2], timestamp) ? current * 2 + 1 : current * 2 + 2;
}
if (compare(heap[current], heap[child], timestamp))
{
break;
}
int temp = heap[current];
heap[current] = heap[child];
heap[child] = temp;
current = child;
}
return 1;
}
void init(int N) {
for (int i = 0; i < MAX_N + SPACE; i++) {
uFollow[i].next = -1;
uPID[i].next = -1;
}
for (int i = 0; i < MAX_P + SPACE; i++) {
uFollows[i].id = 0;
uPIDs[i].id = 0;
pLike[i] = 0;
pTimestamp[i] = 0;
}
followNum = 0;
pidNum = 0;
}
void follow(int uId1, int uId2, int timestamp) {
pushFollow(uId1, uId2);
}
void makePost(int uId, int pId, int timestamp) {
pTimestamp[pId] = timestamp;
pushPid(uId, pId);
}
void like(int pId, int timestamp) {
pLike[pId]++;
}
void getFeed(int uId, int timestamp, int pIdList[]) {
heapInit();
for (int i = uPID[uId].next; i != -1; i = uPIDs[i].next) {
int pid = uPIDs[i].id;
heapPush(pid, timestamp);
}
for (int i = uFollow[uId].next; i != -1; i = uFollows[i].next) {
int id = uFollows[i].id;
for (int j = uPID[id].next; j != -1; j = uPIDs[j].next) {
int pid = uPIDs[j].id;
heapPush(pid, timestamp);
}
}
for (int i = 0; i < 10 && heapSize > 0; i++) {
int pid;
heapPop(&pid, timestamp);
//cout << pid << endl;
pIdList[i] = pid;
}
}
댓글