Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
15 kB
7
Indexable
Never
//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)
	{
		int score = run() ? MARK : 0;
		printf("#%d %d\n", tc, score);
	}

	return 0;
}
//user
#define opt __attribute((optimize("Ofast")))
 
#define MAXL (10)
#define HASH_SIZE 3179
#define HASH_SIZE1 31159
#define MAX_USER 10000
#define MAX_ID 50000 + 1
#define ull unsigned long long
 
opt inline void mStrcpy(char *src, char *des)
{
    int i = 0;
    while ((des[i] = src[i]) != 0)
        ++i;
    return;
}
// define Struct and variable
struct Node
{
    int data;
    Node *nextNode;
} *firstNode[MAX_ID];
struct User
{
    ull name;
    int next, ID;
    char userName[11];
} user[MAX_USER];
struct ID
{
    // key = 1: Post, 2 = Comment, 3 = Reply
    int mID, idMap, key, point;
    int userID;
    int next;
    bool isDelete;
} id[MAX_ID];
struct Score
{
    int score, indexHeap;
} scoreUser[MAX_USER], scorePost[MAX_ID];
int parent[MAX_ID];
 
// Define List, Heap and Map
class LinkedList
{
public:
    opt inline void add(int index, int value)
    {
        Node *newNode = new Node();
        newNode->data = value;
        newNode->nextNode = firstNode[index];
        firstNode[index] = newNode;
    }
    opt inline void del(int index)
    {
        Node *cur = firstNode[index], *prev;
        while (cur != nullptr)
        {
            prev = cur;
            cur = cur->nextNode;
            delete prev;
        }
        firstNode[index] = nullptr;
    }
    opt inline void reset()
    {
        for (int i = 0; i < MAX_ID; ++i)
            del(i);
    }
} linkedList;
class Map
{
private:
    int userMap[HASH_SIZE];
    int cntUser;
 
    int cntID, idMap[HASH_SIZE1];
 
    opt inline ull hash(char str[])
    {
        ull key = 0;
        int i;
        for (i = 0; str[i]; ++i)
            key = (key << 5) + str[i] - 'a' + 1;
 
        while (i <= 10)
        {
            key = (key << 5);
            ++i;
        }
        return key;
    }
 
public:
    opt inline void reset()
    {
        for (int i = 0; i < HASH_SIZE; ++i)
            userMap[i] = -1;
        for (int i = 0; i < HASH_SIZE1; ++i)
            idMap[i] = -1;
        cntID = cntUser = 0;
    }
 
    opt inline int addUser(char str[])
    {
        ull key = hash(str);
        ++cntUser;
        user[cntUser].name = key;
        user[cntUser].ID = cntUser;
        user[cntUser].next = userMap[key % HASH_SIZE];
        userMap[key % HASH_SIZE] = cntUser; // Add LinkedList
        mStrcpy(str, user[cntUser].userName);
        return cntUser;
    }
 
    opt inline int addID(int mID, int key, int nUser, int p)
    {
        ++cntID;
        id[cntID].mID = mID;
        id[cntID].key = key;
        id[cntID].idMap = cntID;
        id[cntID].userID = nUser;
        id[cntID].point = p;
        id[cntID].isDelete = false;
        id[cntID].next = idMap[mID % HASH_SIZE1]; // Add LinkedList
        idMap[mID % HASH_SIZE1] = cntID;
        return cntID;
    }
 
    opt inline int findUser(char str[])
    {
        ull key = hash(str);
        int p = userMap[key % HASH_SIZE];
        while (p != -1 && user[p].name != key)
            p = user[p].next;
        if (p != -1)
            return user[p].ID;
        return -1;
    }
    opt inline int findID(int mID)
    {
        int p = idMap[mID % HASH_SIZE1];
        while (p != -1 && id[p].mID != mID)
            p = id[p].next;
        if (p != -1)
            return id[p].idMap;
        return -1;
    }
 
    opt inline int sizeUser()  { return cntUser; }
    opt inline int sizeID()  { return cntID; }
} map;
struct MAX_HEAP_USER
{
private:
    int dataUser[MAX_USER];
    int nUser;
 
    opt inline bool compare(int i, int j) // i > j
    {
        if (scoreUser[dataUser[i]].score > scoreUser[dataUser[j]].score)
            return true;
        if (scoreUser[dataUser[i]].score == scoreUser[dataUser[j]].score)
            return (user[dataUser[i]].name < user[dataUser[j]].name);
        return false;
    }
    opt inline void swap(int i, int j)
    {
        int id1 = dataUser[i], id2 = dataUser[j];
        dataUser[i] = dataUser[j];
        dataUser[j] = id1;
        scoreUser[id1].indexHeap = j;
        scoreUser[id2].indexHeap = i;
    }
 
public:
    opt inline void upHeap(int k)
    {
        int child = k, parent = k / 2;
        while (parent != 0)
        {
            if (compare(child, parent))
            {
                swap(child, parent);
                child = parent;
                parent = child / 2;
            }
            else
                break;
        }
    }
    opt inline void downHeap(int k)
    {
        int parent = k, child = 2 * k;
        while (child <= nUser)
        {
            if (child + 1 <= nUser && compare(child + 1, child))
                child = child + 1;
            if (compare(child, parent))
            {
                swap(child, parent);
                parent = child;
                child = 2 * parent;
            }
            else
                break;
        }
    }
    opt inline void push(int index)
    {
        nUser++;
        dataUser[nUser] = index;
        scoreUser[index].indexHeap = nUser;
        upHeap(nUser);
    }
    opt inline int pop()
    {
        int id = dataUser[1];
        swap(1, nUser);
        nUser--;
        downHeap(1);
        scoreUser[id].indexHeap = 0;
        return id;
    }
    opt inline void reset() { nUser = 0; }
    opt inline int size() { return nUser; }
} heapUser;
struct MAX_HEAP_POST
{
private:
    int dataPost[MAX_ID];
    int nPost;
 
    opt inline bool compare(int i, int j)
    {
        if (scorePost[dataPost[i]].score > scorePost[dataPost[j]].score)
            return true;
        if (scorePost[dataPost[i]].score == scorePost[dataPost[j]].score)
            return (id[dataPost[i]].mID < id[dataPost[j]].mID);
        return false;
    }
    opt inline void swap(int i, int j)
    {
        int id1 = dataPost[i], id2 = dataPost[j];
        dataPost[i] = dataPost[j];
        dataPost[j] = id1;
        scorePost[id1].indexHeap = j;
        scorePost[id2].indexHeap = i;
    }
 
public:
    opt inline void upHeap(int k)
    {
        int child = k, parent = k / 2;
        while (parent != 0)
        {
            if (compare(child, parent))
            {
                swap(child, parent);
                child = parent;
                parent = child / 2;
            }
            else
                break;
        }
    }
    opt inline void downHeap(int k)
    {
        int parent = k, child = 2 * k;
        while (child <= nPost)
        {
            if (child + 1 <= nPost && compare(child + 1, child))
                child = child + 1;
            if (compare(child, parent))
            {
                swap(child, parent);
                parent = child;
                child = 2 * parent;
            }
            else
                break;
        }
    }
    opt inline void push(int index)
    {
        nPost++;
        dataPost[nPost] = index;
        scorePost[index].indexHeap = nPost;
        upHeap(nPost);
    }
    opt inline int pop()
    {
        int id = dataPost[1];
        swap(1, nPost);
        nPost--;
        downHeap(1);
        scorePost[id].indexHeap = 0;
        return id;
    }
    opt inline void reset() { nPost = 0; }
    opt inline int size() { return nPost; }
} heapPost;
 
opt void init()
{
    heapUser.reset();
    heapPost.reset();
    linkedList.reset();
    map.reset();
    return;
}
 
opt int writeMessage(char mUser[], int mID, int mPoint)
{
    int idUser = map.findUser(mUser);
    if (idUser == -1)
    {
        idUser = map.addUser(mUser);
        scoreUser[idUser].score = mPoint;
        heapUser.push(idUser);
    }
    else
    {
        scoreUser[idUser].score += mPoint;
        heapUser.upHeap(scoreUser[idUser].indexHeap);
    }
 
    int id = map.addID(mID, 1, idUser, mPoint);
    scorePost[id].score = mPoint;
    heapPost.push(id);
    parent[id] = id;
 
    return scoreUser[idUser].score;
}
 
opt int commentTo(char mUser[], int mID, int mTargetID, int mPoint)
{
    int idUser = map.findUser(mUser);
    if (idUser == -1)
    {
        idUser = map.addUser(mUser);
        scoreUser[idUser].score = mPoint;
        heapUser.push(idUser);
    }
    else
    {
        scoreUser[idUser].score += mPoint;
        heapUser.upHeap(scoreUser[idUser].indexHeap);
    }
 
    int targetID = map.findID(mTargetID);
    int idx = map.addID(mID, id[targetID].key + 1, idUser, mPoint);
    parent[idx] = targetID;
    int idPost = parent[targetID];
 
    scorePost[idPost].score += mPoint;
    heapPost.upHeap(scorePost[idPost].indexHeap);
    linkedList.add(idPost, idx);
 
    if (id[targetID].key == 2) // comment
        linkedList.add(targetID, idx);
 
    return scorePost[idPost].score;
}
 
opt int erase(int mID)
{
    int id1 = map.findID(mID);
    if (id[id1].key == 3) // Reply
    {
        int u = id[id1].userID;
        scoreUser[u].score -= id[id1].point;
        heapUser.downHeap(scoreUser[u].indexHeap);
 
        int idPost = parent[parent[id1]];
        scorePost[idPost].score -= id[id1].point;
        heapPost.downHeap(scorePost[idPost].indexHeap);
        id[id1].isDelete = true;
 
        return scorePost[idPost].score;
    }
 
    else if (id[id1].key == 2)
    {
        int idPost = parent[id1];
        Node *curNode = firstNode[id1];
        while (curNode != nullptr)
        {
            int idx = curNode->data;
            curNode = curNode->nextNode;
 
            if (id[idx].isDelete == true)
                continue;
            int u = id[idx].userID;
            scoreUser[u].score -= id[idx].point;
            heapUser.downHeap(scoreUser[u].indexHeap);
            scorePost[idPost].score -= id[idx].point;
            id[idx].isDelete = true;
        }
 
        int u = id[id1].userID;
        scoreUser[u].score -= id[id1].point;
        heapUser.downHeap(scoreUser[u].indexHeap);
        scorePost[idPost].score -= id[id1].point;
 
        id[id1].isDelete = true;
        heapPost.downHeap(scorePost[idPost].indexHeap);
        return scorePost[idPost].score;
    }
    else // id1 is Post (id[id1].key == 1))
    {
        Node *curNode = firstNode[id1];
        while (curNode != nullptr)
        {
            int idx = curNode->data;
            curNode = curNode->nextNode;
            if (id[idx].isDelete == true)
                continue;
            int u = id[idx].userID;
            scoreUser[u].score -= id[idx].point;
            heapUser.downHeap(scoreUser[u].indexHeap);
        }
 
        id[id1].isDelete = true;
        scorePost[id1].score = 0;
        heapPost.downHeap(scorePost[id1].indexHeap);
 
        int userID = id[id1].userID;
        scoreUser[userID].score -= id[id1].point;
        heapUser.downHeap(scoreUser[userID].indexHeap);
 
        return scoreUser[userID].score;
    }
}
 
opt void getBestMessages(int mBestMessageList[])
{
    int target[5], i;
    for (i = 0; i < 5; ++i)
        target[i] = heapPost.pop();
    for (i = 0; i < 5; ++i)
        heapPost.push(target[i]);
    for (i = 0; i < 5; ++i)
        mBestMessageList[i] = id[target[i]].mID;
    return;
}
 
opt void getBestUsers(char mBestUserList[][MAXL + 1])
{
    int target[5], i;
    for (i = 0; i < 5; ++i)
        target[i] = heapUser.pop();
    for (i = 0; i < 5; ++i)
        heapUser.push(target[i]);
    for (i = 0; i < 5; ++i)
        mStrcpy(user[target[i]].userName, mBestUserList[i]);
    return;
}
//input
25 100
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
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