Untitled
unknown
plain_text
a year ago
14 kB
3
Indexable
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.
#define MX 50021
#define MU 10007
#define ll long long
#define f(i,x,n) for(register int i=x;i<n;i++)
struct Msg{
int id, uid, pid, cid, point, total, hid, nextH, nextC, ok;
bool operator>(Msg& node){
return total==node.total ? id<node.id : total>node.total;
}
}M[MX];
int m, mapM[MX];
struct HeapMsg{
int N, H[MX];
void up(int id){
int tmp = H[id];
while(id){
int t = (id-1)/2;
if(M[H[t]]>M[tmp]) break;
H[id] = H[t];
M[H[id]].hid = id;
id = t;
}
H[id] = tmp;
M[tmp].hid = id;
}
void add(int Id){
H[N] = Id;
up(N++);
}
void down(int id){
int tmp = H[id];
int t = 2*id+1;
while(t<N){
if(t+1<N&&M[H[t+1]]>M[H[t]]) t++;
if(M[tmp]>M[H[t]]) break;
H[id] = H[t];
M[H[id]].hid = id;
id = t;
t = 2*id+1;
}
H[id] = tmp;
M[tmp].hid = id;
}
void del(int id){
H[id] = H[--N];
down(id);
up(id);
}
void mod(int id){
down(id);
up(id);
}
}hpM;
struct User{
ll val;
int point, hid, next;
bool operator>(User& node){
return point==node.point ? val<node.val : point>node.point;
}
void name(char *s){
int i = 0;
for(int j=9;j>-1;j--){
int k = (val>>(j*5))&31;
if(!k) break;
s[i++] = k+96;
}
s[i] = 0;
}
}U[MU];
int u, mapU[MU], h;
ll v;
int getU(char *s){
v = 0;
for(int i=0,j=9;s[i];i++,j--){
v |= (ll)(s[i]-96)<<(j*5);
}
h = v%MU;
int id = mapU[h];
while(id&&U[id].val!=v) id = U[id].next;
return id;
}
struct HeapUser{
int N, H[MU];
void up(int id){
int tmp = H[id];
while(id){
int t = (id-1)/2;
if(U[H[t]]>U[tmp]) break;
H[id] = H[t];
U[H[id]].hid = id;
id = t;
}
H[id] = tmp;
U[tmp].hid = id;
}
void add(int Id){
H[N] = Id;
up(N++);
}
void down(int id){
int tmp = H[id];
int t = 2*id+1;
while(t<N){
if(t+1<N&&U[H[t+1]]>U[H[t]]) t++;
if(U[tmp]>U[H[t]]) break;
H[id] = H[t];
U[H[id]].hid = id;
id = t;
t = 2*id+1;
}
H[id] = tmp;
U[tmp].hid = id;
}
void del(){
H[0] = H[--N];
down(0);
}
void mod(int id){
down(id);
up(id);
}
}hpU;
void init(){
m = u = 1;
hpM.N = hpU.N = 0;
f(i,0,MX) mapM[i] = 0;
f(i,0,MU) mapU[i] = 0;
}
int writeMessage(char mUser[], int mID, int mPoint){
int id = getU(mUser);
if(!id){
U[u].val = v;
U[u].point = mPoint;
U[u].next = mapU[h];
mapU[h] = u;
id = u++;
hpU.add(id);
}else{
U[id].point += mPoint;
hpU.mod(U[id].hid);
}
h = mID%MX;
M[m].id = mID;
M[m].uid = id;
M[m].pid = M[m].cid = M[m].nextC = 0;
M[m].point = M[m].total = mPoint;
M[m].nextH = mapM[h];
mapM[h] = m;
M[m].ok = 1;
hpM.add(m++);
return U[id].point;
}
int commentTo(char mUser[], int mID, int mTargetID, int mPoint){
int id = getU(mUser);
if(!id){
U[u].val = v;
U[u].point = mPoint;
U[u].next = mapU[h];
mapU[h] = u;
id = u++;
hpU.add(id);
}else{
U[id].point += mPoint;
hpU.mod(U[id].hid);
}
int pid = mapM[mTargetID%MX];
while(M[pid].id!=mTargetID) pid = M[pid].nextH;
h = mID%MX;
M[m].id = mID;
M[m].uid = id;
M[m].pid = pid;
M[m].nextC = M[pid].cid;
M[pid].cid = m;
M[m].cid = 0;
M[m].point = M[m].total = mPoint;
M[m].nextH = mapM[h];
mapM[h] = m;
M[m++].ok = 1;
M[pid].total += mPoint;
if(M[pid].pid){
pid = M[pid].pid;
M[pid].total += mPoint;
}
hpM.mod(M[pid].hid);
return M[pid].total;
}
void eraseD(int id){
if(M[id].ok){
M[id].ok = 0;
U[M[id].uid].point -= M[id].point;
hpU.mod(U[M[id].uid].hid);
int cid = M[id].cid;
while(cid){
eraseD(cid);
cid = M[cid].nextC;
}
}
}
int erase(int mID){
int id = mapM[mID%MX];
while(M[id].id!=mID) id = M[id].nextH;
eraseD(id);
if(!M[id].pid){
hpM.del(M[id].hid);
return U[M[id].uid].point;
}
int pid = M[id].pid;
M[pid].total -= M[id].total;
if(M[pid].pid){
pid = M[pid].pid;
M[pid].total -= M[id].total;
}
hpM.mod(M[pid].hid);
return M[pid].total;
}
int A[5];
void getBestMessages(int mBestM[]){
f(i,0,5){
A[i] = hpM.H[0];
mBestM[i] = M[A[i]].id;
hpM.del(0);
}
f(i,0,5) hpM.add(A[i]);
}
void getBestUsers(char mBestU[][11]){
f(i,0,5){
A[i] = hpU.H[0];
U[A[i]].name(mBestU[i]);
hpU.del();
}
f(i,0,5) hpU.add(A[i]);
}