Untitled
unknown
plain_text
2 years ago
20 kB
6
Indexable
[Problem Description]
An electronic bulletin board allows users to publish posts.
Users are allowed to write comments on the published posts. Also, they can add replies to the comments. However, they are not allowed to reply to replies.
Posts, comments and replies may be deleted. When a post is deleted, all comments and replies added to it are deleted. When a comment is deleted, all replies added to it are deleted.
All users have different names. In other words, same name means same user.
Posts, comments, and replies have different IDs. In other words, there are no duplicate IDs among all IDs of posts, comments, and replies.
Each of posts, comments, and replies gets points.
Using the points of posts, comments, and replies, the bulletin board shows the best post or user.
Adding the points of a post, and all points of comments and replies added to the post, the best post section shows, in descending order, the top 5 posts in terms of the highest sum of points.
In the case of same sum of points, the post with a lower ID number has a higher rank.
Adding the points of posts, comments, and replies each user wrote, the best user section shows, in descending order, the top 5 users in terms of the highest sum of points.
In the case of same sum of points, the user whose name precedes those of others in lexicographic order is ranked higher.
Deleted posts, comments, and replies are not counted, when adding points.
Implement each required function by referring to the following API description.
※ The function signature below is based on C/C++. As for other languages, refer to the provided Main and User Code.
The following is the description of API to be written in the User Code.
void init()
This initialization function for each test case is called once in the beginning of each test case.
No posts are published on the electronic bulletin board at first.
int writeMessage(char mUser[], int mID, int mPoint)
A user whose name is mUser writes and publishes a post which has the ID of mID and points of mPoint. Return the total points the user got after publishing the post.
The total points of the user equal to the sum of all points of posts, comments, and replies the user wrote. Deleted posts, comments, and replies do not count.
It is guaranteed that mID passed when calling the function is not a value passed already during previous calls.
mUser is a character string consisting of English lower case letters. Its length is greater than or equal to 1 but less than or equal to 10.
※ As for C++ and Java, the character string ends with ‘\0’ which is not included in the length. As for Python, it is passed as an object of str.
Parameters
mUser : the name of the user to write a post (1 ≤ |mUser| ≤ 10, |a| means the length of the character string a.)
mID : the ID of the post to be written (1 ≤ mID ≤ 1,000,000,000)
mPoint : the points of the post to be written (1 ≤ mPoint ≤ 10,000)
Returns
the total points of user mUser after publishing a new post
int commentTo(char mUser[], int mID, int mTargetID, int mPoint)
A user named mUser adds a comment or a reply, which has mPoint points and the ID of mID, to a post or a comment with the ID of mTargetID.
If mTargetID is the ID of a post, add the comment mID to the post mTargetID, and return the sum of points of the post mTargetID.
If mTargetID is the ID of a comment, add the reply mID to the comment mTargetID, and return the sum of points of the post to which the comment mTargetID is added.
The sum of points of a post is calculated by adding the point of the post and the points of replies and comments added to the post. Do not add points of deleted comments and replies.
It is guaranteed that mTargetID passed when calling the function is the ID of a post or a comment which is not deleted.
It is guaranteed that mID passed when calling the function is not a value passed already during previous calls.
mUser is a character string consisting of English lower case letters and the length is greater than or equal to 1 but less than or equal to 10.
Parameters
mUser : the name of the user to write a comment or a reply (1 ≤ |mUser| ≤ 10)
mID : the ID of the comment or reply (1 ≤ mID ≤ 1,000,000,000)
mTargetID : the ID of the post or comment to which a comment or reply is to be added (1 ≤ mTargetID ≤ 1,000,000,000)
mPoint : the points of the comment or reply (1 ≤ mPoint ≤ 10,000)
Returns
the sum of points of the post to which a comment or reply is added after publishing the post
int erase(int mID)
Delete the post, comment, or reply with the ID of mID.
If mID is the ID of a post, return the total points of the user who wrote the deleted post mID.
If mID is the ID of a comment or a reply, return the sum of points of the post to which the deleted comment or reply was added.
It is guaranteed that mID is the ID of a published post or comment that is not deleted.
Parameters
mID : the ID of a post, comment, or reply to be deleted (1 ≤ mID ≤ 1,000,000,000)
Returns
If mID is the ID of a post, the total points of the user
If mID is the ID of a comment or a reply, the sum of points of the post
void getBestMessages(int mBestMessageList[])
On mBestMessageList, save, in descending order, the ID of the top 5 posts in terms of the highest sum of points. In the case of same sum of points, the post with a lower ID is ranked higher.
On mBestMessageList[i – 1], save the ID of the post with the ith highest sum of points. (1 ≤ i ≤ 5)
It is guaranteed that 5 or more posts are published on the bulletin board when the function is called.
Parameters
mBestMessageList : the array on which the IDs of posts with the highest sum of points will be saved
void getBestUsers(char mBestUserList[][])
On mBestUserList, save, in descending order, the name of the top 5 users in terms of the highest total points. In the case of same total points, the user whose name comes first in lexicographic order is ranked higher.
On mBestUserList[i – 1], save the name of the user with the ith highest total points. (1 ≤ i ≤ 5)
※ As for C++ and Java, save ‘\0’ at the end of the string. As for Python, save str object.
It is guaranteed that when the function is called, there are 5 or more users who wrote a post, comment, or reply which is not deleted.
Parameters
mBestUserList : the array on which the name of users with the highest total points will be saved
[Example]
Let’s think about the case where functions are called as in [Table 1].
Order
Function
Return
Figure
1
init()
2
writeMessage(“aaa”, 1, 10)
10
3
writeMessage(“bbb”, 2, 5)
5
4
commentTo(“ccc”, 3, 1, 5)
15
5
commentTo(“ddd”, 4, 1, 3)
18
6
commentTo(“eee”, 5, 3, 4)
22
7
getBestUsers()
{“aaa”, “bbb”, “ccc”, “eee”, “ddd”}
[Fig. 2]
8
writeMessage(“ccc”, 6, 20)
25
9
writeMessage(“bbb”, 7, 13)
18
10
writeMessage(“aaa”, 8, 20)
30
11
getBestMessages()
{1, 6, 8, 7, 2}
[Fig. 3]
12
writeMessage(“fff”, 9, 1)
1
13
commentTo(“ddd”, 10, 6, 10)
30
14
erase(3)
13
15
getBestUsers()
{“aaa”, “ccc”, “bbb”, “ddd”, “fff”}
[Fig. 4]
16
erase(6)
0
17
commentTo(“ccc”, 20, 2, 35)
40
18
commentTo(“fff”, 30, 9 , 14)
15
19
getBestMessages()
{2, 8, 9, 1, 7}
[Fig. 5]
20
getBestUsers()
{“ccc”, “aaa”, “bbb”, “fff”, “ddd”}
[Fig. 5]
[Table 1]
[Fig. 2] shows the sum of points of users when function getBestUsers() is called in order 7. The number in parenthesis in [Fig. 2] means the point.
[Fig. 3] shows the sum of points of posts when function getBestMessages() is called in order 11.
[Fig. 4] shows the sum of points of users when function getBestUsers() is called in order 15.
[Fig. 5] shows the sum of points of posts when function getBestMessages() is called in order 19 and the sum of points of users when function getBestUsers() is called in order 20.
[Constraints]
1. For each test case, init() is called once in the beginning.
2. For each test case, the number of users is less than or equal to 10,000.
3. For each test case, all functions may be called up to 50,000 times.
[Input and Output]
As the input and output are processed in the provided code in the Main, they are not processed separately in the User Code.
The output result for the sample input is provided in the form of “#TC number result.” It is Pass if the result is 100; it is Fail if it is 0.
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
#define CMD_INIT (100)
#define CMD_WRITE_MESSAGE (200)
#define CMD_COMMENT_TO (300)
#define CMD_ERASE (400)
#define CMD_GET_BEST_MESSAGES (500)
#define CMD_GET_BEST_USERS (600)
#define MAXL (10)
extern void init();
extern int writeMessage(char mUser[], int mID, int mPoint);
extern int commentTo(char mUser[], int mID, int mTargetID, int mPoint);
extern int erase(int mID);
extern void getBestMessages(int mBestMessageList[]);
extern void getBestUsers(char mBestUserList[][MAXL + 1]);
static int mstrcmp(char a[], char b[])
{
int idx = 0;
while (a[idx] != '\0' && a[idx] == b[idx])
++idx;
return a[idx] - b[idx];
}
static bool run()
{
int Q;
int mID, mTargetID, mPoint;
char mUser[MAXL + 1];
char mBestUserList[5][MAXL + 1];
int mBestMessageList[5];
int ret = -1, ans;
scanf("%d", &Q);
bool okay = false;
for (int q = 0; q < Q; ++q)
{
int cmd;
scanf("%d", &cmd);
switch(cmd)
{
case CMD_INIT:
init();
okay = true;
break;
case CMD_WRITE_MESSAGE:
scanf("%s %d %d", mUser, &mID, &mPoint);
ret = writeMessage(mUser, mID, mPoint);
scanf("%d", &ans);
if (ret != ans)
okay = false;
break;
case CMD_COMMENT_TO:
scanf("%s %d %d %d", mUser, &mID, &mTargetID, &mPoint);
ret = commentTo(mUser, mID, mTargetID, mPoint);
scanf("%d", &ans);
if (ret != ans)
okay = false;
break;
case CMD_ERASE:
scanf("%d", &mID);
ret = erase(mID);
scanf("%d", &ans);
if (ret != ans)
okay = false;
break;
case CMD_GET_BEST_MESSAGES:
getBestMessages(mBestMessageList);
for (int i = 0; i < 5; ++i)
{
scanf("%d", &ans);
if (mBestMessageList[i] != ans)
okay = false;
}
break;
case CMD_GET_BEST_USERS:
getBestUsers(mBestUserList);
for (int i = 0; i < 5; ++i)
{
scanf("%s", mUser);
if (mstrcmp(mBestUserList[i], mUser) != 0)
okay = false;
}
break;
default:
okay = false;
break;
}
}
return okay;
}
int main()
{
setbuf(stdout, NULL);
//freopen("sample_input.txt", "r", stdin);
int TC, MARK;
scanf("%d %d", &TC, &MARK);
for (int tc = 1; tc <= TC; ++tc)
{
int score = run() ? MARK : 0;
printf("#%d %d\n", tc, score);
}
return 0;
}
#define MAX_POST 50001
#define MAX_USER 10001
#define MAX_HASH1 10007
#define MAX_HASH2 50021
#define MAX_L 11
//String utils:
void strCpy(char *t, char *s)
{
while (*t++ = *s++)
;
}
long long hash(char* name)
{
long long ret = 0;
for (register int i = 0; name[i]; i++)
ret += (long long)(name[i] - 96) << (5 * (9 - i));
return ret;
}
struct BasicInfo {//Common info of all objects
long long id; //for users, info id is hash value of their name; for messages, comments, replies, info id is their id.
int totalPoint;
int objectIdx; //index of objects in pool arrays
BasicInfo* next; //For hash map
int heapIdx; //For heap
} infos[MAX_POST + MAX_USER];
int objectCnt;
struct User {
char name[MAX_L];
BasicInfo* info;
} users[MAX_USER];
int userNum;
struct Post { //A post can be message, comment or reply
int point;
BasicInfo* info;
Post* parent;
User* user;
//For linked list
Post* next;
Post* firstChild;
} posts[MAX_POST];
int postNum;
//Heaps
BasicInfo* userInfoHeap[MAX_USER];
int userHeapSize;
BasicInfo* postInfoHeap[MAX_POST];
int postHeapSize;
bool isBetter(BasicInfo* info1, BasicInfo* info2)
{
return info1->totalPoint > info2->totalPoint || (info1->totalPoint == info2->totalPoint && info1->id < info2->id);
}
void upHeapify(BasicInfo* heap[], int pos)
{
register BasicInfo* curr = heap[pos];
for( ; pos > 1 && isBetter(curr, heap[pos >> 1]); pos >>= 1) {
heap[pos] = heap[pos >> 1];
heap[pos]->heapIdx = pos;
}
heap[pos] = curr;
heap[pos]->heapIdx = pos;
}
void downHeapify(BasicInfo* heap[], int size, int pos)
{
register BasicInfo* curr = heap[pos];
register int child;
while ((child = pos << 1) <= size) {
if (child < size && isBetter(heap[child + 1], heap[child]))
child++;
if (isBetter(heap[child], curr)) {
heap[pos] = heap[child];
heap[pos]->heapIdx = pos;
pos = child;
} else break;
}
heap[pos] = curr;
heap[pos]->heapIdx = pos;
}
void heapPush(BasicInfo* heap[], int &size, BasicInfo* info)
{
heap[++size] = info;
upHeapify(heap, size);
}
void heapUpdate(BasicInfo* heap[], int size, BasicInfo* info)
{
register int pos = info->heapIdx;
upHeapify(heap, pos);
downHeapify(heap, size, pos);
}
void heapRemove(BasicInfo* heap[], int &size, BasicInfo* info)
{
register int pos = info->heapIdx;
heap[pos] = heap[size--];
heap[pos]->heapIdx = pos;
heapUpdate(heap, size, heap[pos]);
}
BasicInfo* heapPop(BasicInfo* heap[], int &size)
{
BasicInfo* ret = heap[1];
heapRemove(heap, size, heap[1]);
return ret;
}
//HashMaps
BasicInfo* userInfoMap[MAX_HASH1];
BasicInfo* postInfoMap[MAX_HASH2];
Post* findPost(int postId)
{
for (BasicInfo* info = postInfoMap[postId % MAX_HASH2]; info; info = info->next)
if (postId == info->id)
return &posts[info->objectIdx];
return nullptr;
}
User* findUser(char *name)
{
long long hashVal = hash(name);
for (BasicInfo* info = userInfoMap[hashVal % MAX_HASH1]; info; info = info->next)
if (hashVal == info->id)
return &users[info->objectIdx];
//If user not exist, create new user and user info
BasicInfo* info = &infos[objectCnt++];
info->id = hashVal;
info->objectIdx = userNum;
info->totalPoint = 0;
//Add to hash map
register int idx = hashVal % MAX_HASH1;
info->next = userInfoMap[idx];
userInfoMap[idx] = info;
//Add to end of heap, will be updated later
userInfoHeap[++userHeapSize] = info;
info->heapIdx = userHeapSize;
//Create new user
strCpy(users[userNum].name, name);
users[userNum].info = info;
return &users[userNum++];
}
int addNewPost(User* user, int mID, int mPoint, Post* mParent)
{
user->info->totalPoint += mPoint;
heapUpdate(userInfoHeap, userHeapSize, user->info);
//Create new post info and add to hash map
BasicInfo* postInfo = &infos[objectCnt++];
postInfo->id = mID;
postInfo->totalPoint = mPoint;
postInfo->objectIdx = postNum;
register int idx = mID % MAX_HASH2;
postInfo->next = postInfoMap[idx];
postInfoMap[idx] = postInfo;
//Create new post
Post* post = &posts[postNum++];
post->info = postInfo;
post->point = mPoint;
post->user = user;
post->firstChild = nullptr;
post->parent = mParent;
if (mParent) { //this post is a comment or reply
post->next = mParent->firstChild;
mParent->firstChild = post;
mParent->info->totalPoint += mPoint;
if (mParent->parent) { //this is a reply
mParent = mParent->parent;
mParent->info->totalPoint += mPoint;
}
heapUpdate(postInfoHeap, postHeapSize, mParent->info);
return mParent->info->totalPoint;
}
//this post is a message
heapPush(postInfoHeap, postHeapSize, postInfo);
post->next = nullptr;
return user->info->totalPoint;
}
void init()
{
objectCnt = userNum = postNum = userHeapSize = postHeapSize = 0;
for (register int i = 0; i < MAX_HASH1; i++)
userInfoMap[i] = nullptr;
for (register int i = 0; i < MAX_HASH2; i++)
postInfoMap[i] = nullptr;
}
int writeMessage(char mUser[], int mID, int mPoint)
{
User* user = findUser(mUser);
return addNewPost(user, mID, mPoint, nullptr);
}
int commentTo(char mUser[], int mID, int mTargetID, int mPoint)
{
User* user = findUser(mUser);
Post* target = findPost(mTargetID);
return addNewPost(user, mID, mPoint, target);
}
//When erasing post, traversal all descendants and update their user's point
void updateUserPoint(Post* post)
{
post->user->info->totalPoint -= post->point;
heapUpdate(userInfoHeap, userHeapSize, post->user->info);
for (register Post* child = post->firstChild; child; child = child->next)
updateUserPoint(child);
}
int erase(int mID)
{
Post* post = findPost(mID);
updateUserPoint(post);
Post* parent = post->parent;
if (parent) {//this post is a comment or reply
//delete from parent's list
if (post == parent->firstChild)
parent->firstChild = post->next;
else {
for (register Post* i = parent->firstChild; i->next; i = i->next) {
if (post == i->next) {
i->next = i->next->next;
break;
}
}
}
parent->info->totalPoint -= post->info->totalPoint;
if (parent->parent) { //this post is a reply
parent = parent->parent;
parent->info->totalPoint -= post->info->totalPoint;
}
heapUpdate(postInfoHeap, postHeapSize, parent->info);
return parent->info->totalPoint;
}
//this is a message
heapRemove(postInfoHeap, postHeapSize, post->info);
return post->user->info->totalPoint;
}
BasicInfo* bestInfos[5];
void getBestMessages(int mBestMessageList[])
{
for (register int i = 0; i < 5; i++) {
bestInfos[i] = heapPop(postInfoHeap, postHeapSize);
mBestMessageList[i] = bestInfos[i]->id;
}
for (register int i = 0; i < 5; i++)
heapPush(postInfoHeap, postHeapSize, bestInfos[i]);
}
void getBestUsers(char mBestUserList[][MAX_L])
{
for (register int i = 0; i < 5; i++) {
bestInfos[i] = heapPop(userInfoHeap, userHeapSize);
strCpy(mBestUserList[i], users[bestInfos[i]->objectIdx].name);
}
for (register int i = 0; i < 5; i++)
heapPush(userInfoHeap, userHeapSize, bestInfos[i]);
}
Editor is loading...