Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
11 kB
2
Indexable
Never
//user
#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 hash1(char* p)
//{
//    long long rtn = 0;
//    char c;
//    while ((c=*p++))
//    {
//        rtn = (rtn << 5) + (c - 'a') + 1;
//    }
// 
//    return rtn;
//} 
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)
{
	//hash1(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
	//heapPush(userInfoHeap, userHeapSize, info);
    userInfoHeap[++userHeapSize] = info;
    userInfoHeap[userHeapSize]->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] = (int)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]);
}
//main
#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("Text.txt", "r", stdin);

	int TC, MARK;

	scanf("%d %d", &TC, &MARK);
	for (int tc = 1; tc <= TC; ++tc)
	{
		//if (tc==2)
		int score = run() ? MARK : 0;
		printf("#%d %d\n", tc, score);
	}

	return 0;
}
//input
25 100
27
100
200 t 424 9 9
200 mpky 7 7 7
300 l 492 7 1 8
300 p 860451 424 6 15
300 hv 2158753 860451 2 17
300 t 8225355 492 1 9
300 hv 9 860451 2 19
200 kzwgyt 56 9 9
200 mpky 90388 6 13
400 492 7
600 mpky kzwgyt t p hv
200 geur 905 1 1
200 geur 558 1 2
500 424 56 7 90388 558
300 mpky 532037 90388 6 12
300 geur 4380 532037 8 20
300 kzwgyt 580534984 905 5 6
200 l 12838 4 4
300 p 95050 90388 6 26
200 kzwgyt 81 1 15
300 zfu 2 424 8 27
400 12838 0
200 mpky 110748 1 20
200 xp 88696 3 3
500 424 90388 56 7 905
600 mpky kzwgyt p geur t
20
100
200 aaa 1 10 10
200 bbb 2 5 5
300 ccc 3 1 5 15
300 ddd 4 1 3 18
300 eee 5 3 4 22
600 aaa bbb ccc eee ddd
200 ccc 6 20 25
200 bbb 7 13 18
200 aaa 8 20 30
500 1 6 8 7 2
200 fff 9 1 1
300 ddd 10 6 10 30
400 3 13
600 aaa ccc bbb ddd fff
400 6 0
300 ccc 20 2 35 40
300 fff 30 9 14 15
500 2 8 9 1 7
600 ccc aaa bbb fff ddd