Untitled
unknown
plain_text
a year ago
17 kB
10
Indexable
------------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("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;
}
--------------USER----------------------
#define MAXL (10)
#define MAX_USER 10007
#define MAX_MESSAGE 50007
#define HASH_SIZE 20007
#define HEAP_SIZE 50007
#define ull unsigned long long
class Node{
public:
ull id;
Node* hashNext;
int heapIdx;
bool deleted;
int point;
int totalPoints;
bool operator==(const Node& o){
return (o.deleted? false : (o.id == id));
}
bool operator<(const Node& o){
return ((totalPoints == o.totalPoints)? id > o.id : totalPoints < o.totalPoints);
}
};
class Message : public Node{
public:
Message* parent;
Message* child;
Message* next;
int type;
Node* user;
void init(int mId, int mPoint, int mType, Node* mUser, Message* mParent){
id = mId;
point = mPoint;
totalPoints = mPoint;
type = mType;
user = mUser;
parent = mParent;
hashNext = 0;
next = child = 0;
heapIdx = deleted = 0;
}
};
class User : public Node{
public:
char sName[11];
int length;
void init(char* str){
heapIdx = totalPoints = 0;
deleted = false;
hashNext = 0;
id = getHash(str);
length = 0;
while(str[length] != '\0'){
sName[length] = str[length];
length++;
}
sName[length++] = '\0';
}
//ull getHash(char* str){
// ull ret = 0;
// while(*str != '\0'){
// ret = ret * 31 + (*str - 'a' + 1);
// str++;
// }
// return ret;
//}
ull getHash(char* s)
{
ull ret = 0;
int pow = 9;
while (*s != '\0')
{
ull c = (*s - 'a' + 1);
ret = (ret | (c << (pow * 5)));
pow--;
s++;
}
return ret;
}
};
class HashMap{
public:
Node* hm[HASH_SIZE];
void reset(){
for(int i = 0 ; i < HASH_SIZE; i++){
hm[i] = 0;
}
}
void insert(Node* node){
int h = node->id % HASH_SIZE;
node->hashNext = hm[h];
hm[h] = node;
}
Node* get(Node* node){
int h = node->id % HASH_SIZE;
Node* n = hm[h];
while(n && !(*node == *n)) n = n->hashNext;
return n;
}
};
class IndexedHeap{
public:
Node* hp[HEAP_SIZE];
int idx;
void reset() {idx = 0;}
void down(Node* node){
int id = node->heapIdx;
int child = 2*id + 1;
while(child < idx){
if(child + 1 < idx && (*hp[child] < *hp[child+1])) child++;
if(*hp[child] < *node) break;
hp[id] = hp[child];
hp[id]->heapIdx = id;
id = child;
child = 2*id + 1;
}
hp[id] = node;
node->heapIdx = id;
}
void up(Node* node){
int id = node->heapIdx;
while(id){
int parent = (id - 1)/2;
if(*node < *hp[parent]) break;
hp[id] = hp[parent];
hp[id]->heapIdx = id;
id = parent;
}
hp[id] = node;
node->heapIdx = id;
}
void push(Node* node){
node->heapIdx = idx;
hp[idx] = node;
up(hp[idx++]);
}
void update(Node* node){
int id = node->heapIdx;
down(hp[id]);
up(hp[id]);
}
Node* pop(){
Node* node = hp[0];
hp[0] = hp[--idx];
hp[0]->heapIdx = 0;
down(hp[0]);
return node;
}
};
Message messages[MAX_MESSAGE];
int msgIdx;
User users[MAX_USER];
int userIdx;
HashMap messageHm, userHm;
IndexedHeap messageHp, userHp;
void init()
{
msgIdx = userIdx = 2;
messageHm.reset();
userHm.reset();
messageHp.reset();
userHp.reset();
return;
}
Node* getUser(char* mUser)
{
auto& user = users[userIdx];
user.init(mUser);
Node* ptr = userHm.get(&user);
if (ptr == 0)
{
userHm.insert(&user);
userHp.push(&user);
ptr = &user;
userIdx++;
}
return ptr;
}
int writeMessage(char mUser[], int mID, int mPoint)
{
auto user = getUser(mUser);
user->totalPoints += mPoint;
userHp.update(user);
auto msg = &messages[msgIdx++];
msg->init(mID, mPoint, 0, user, 0);
messageHp.push(msg);
messageHm.insert(msg);
return user->totalPoints;
}
int commentTo(char mUser[], int mID, int mTargetID, int mPoint)
{
auto user = getUser(mUser);
user->totalPoints += mPoint;
userHp.update(user);
messages[1].id = mTargetID;
Message* pmsg = (Message*)messageHm.get(&messages[1]);
Message* message = &messages[msgIdx++];
message->init(mID, mPoint, pmsg->type+1, user, pmsg);
messageHm.insert(message);
if(pmsg->child == 0) pmsg->child = message;
else{
Message* m = pmsg->child;
pmsg->child = message;
message->next = m;
}
pmsg->totalPoints += mPoint;
if(pmsg->parent) {
pmsg = pmsg->parent;
pmsg->totalPoints += mPoint;
}
messageHp.update(pmsg);
return pmsg->totalPoints;
}
int erase(int mID)
{
messages[1].id = mID;
Message* msg = (Message*)messageHm.get(&messages[1]);
msg->user->totalPoints -= msg->point;
userHp.update(msg->user);
msg->deleted = true;
if(msg->child){
Message* ch1 = msg->child;
while(ch1){
if(!ch1->deleted){
ch1->user->totalPoints -= ch1->point;
userHp.update(ch1->user);
ch1->deleted = true;
if(ch1->child){
Message* ch2 = ch1->child;
while(ch2){
if(!ch2->deleted){
ch2->user->totalPoints-= ch2->point;
userHp.update(ch2->user);
ch2->deleted = true;
}
ch2 = ch2->next;
}
}
}
ch1=ch1->next;
}
}
if(msg->type == 0) return msg->user->totalPoints;
int p = msg->totalPoints;
while(msg->type != 0){
msg = msg->parent;
msg ->totalPoints -= p;
}
messageHp.update(msg);
return msg->totalPoints;
}
void getBestMessages(int mBestMessageList[])
{
int i = 0;
Message* msg[5];
while(i < 5){
msg[i] = (Message*) messageHp.pop();
if(msg[i]->deleted) continue;
mBestMessageList[i] = msg[i]->id;
i++;
}
while(i > 0) messageHp.push(msg[--i]);
}
void getBestUsers(char mBestUserList[][MAXL + 1])
{
int i = 0;
User* user[5];
while(i < 5){
user[i] = (User*)userHp.pop();
if(user[i]->deleted) continue;
auto u = user[i];
for(int j = 0; j < u->length; j++) mBestUserList[i][j] = u->sName[j];
i++;
}
while(i > 0) userHp.push(user[--i]);
return;
}
-------------------INPUT---------------------------
#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]);
}