Untitled
unknown
plain_text
a year ago
6.3 kB
5
Indexable
#include <iostream> using namespace std; #include <vector> #include <string> #include <unordered_map> #include <set> static const int MAXL = 16; const int MAX_APP = 10005; const int MAX_USER = 10005; struct RESULT { char mApp[5][MAXL]; }; struct Rating{ int score; //rating of app int numUser; string nameApp; } rating_pool[MAX_APP]; unordered_map<string, Rating*> hashApp; // convert app name to Rating unordered_map<string, int> users[MAX_USER]; // users[i] rates app (app_name) rating score bool is_banned[MAX_USER]; // whether user i is banned struct scoreCompare { int getAvgScore(int total, int num) { if (num == 0) return 0; return ((float)total/num)*10; } bool operator() (Rating *p1, Rating *p2) { int avg1 = getAvgScore(p1->score, p1->numUser); int avg2 = getAvgScore(p2->score, p2->numUser); if (avg1 == avg2) { return p1->nameApp < p2->nameApp; } return avg1 > avg2; } }; struct numberCompare { public: bool operator() (Rating *p1, Rating *p2) { if(p1->numUser == p2->numUser){ return p1->nameApp < p2->nameApp; } return (p1->numUser > p2->numUser); //lay max so luong } }; set<Rating*, scoreCompare> Score; // sort Rating following by scoreCompare set<Rating*, numberCompare> Number; // sort Rating following by numberCompare static void mstrcpy(char dest[], const char src[]) { int i = 0; while (src[i] != '\0') { dest[i] = src[i]; i++; } dest[i] = src[i]; } void init(int N, const char mApp[][MAXL]) { hashApp.clear(); Score.clear(); Number.clear(); for(int i=0; i<N; i++){ string name = mApp[i]; rating_pool[i].nameApp = mApp[i]; rating_pool[i].numUser = 0; rating_pool[i].score = 0; hashApp[name] = &rating_pool[i]; Score.insert(&rating_pool[i]); Number.insert(&rating_pool[i]); } for (int i=0; i<MAX_USER; i++) { is_banned[i] = false; users[i].clear(); } } void addRating(int mUser, const char mApp[MAXL], int mScore) { if (is_banned[mUser]) return; string nameApp = mApp; Rating* p = hashApp[nameApp]; Score.erase(p); Number.erase(p); if (users[mUser].count(mApp) != 0) { // user rated app p->score = p->score - users[mUser][mApp] + mScore; users[mUser][mApp] = mScore; } else { p->score = p->score + mScore; ++p->numUser; users[mUser].insert(make_pair(mApp, mScore)); } Score.insert(p); Number.insert(p); } void deleteRating(int mUser, const char mApp[MAXL]) { string nameApp = mApp; Rating* p = hashApp[nameApp]; Score.erase(p); Number.erase(p); --p->numUser; p->score -= users[mUser][mApp]; users[mUser].erase(mApp); Score.insert(p); Number.insert(p); } void banUser(int mUser) { if (is_banned[mUser]) return; is_banned[mUser] = true; for (pair<string, int> app : users[mUser]) { Rating* p = hashApp[app.first]; Score.erase(p); Number.erase(p); --p->numUser; p->score -= app.second; Score.insert(p); Number.insert(p); } } RESULT sortByScore() { RESULT ret = {}; int i = 0; for (auto it = Score.begin(); it != Score.end(); it++) { if (i == 5) break; mstrcpy(ret.mApp[i], (*it)->nameApp.c_str()); i++; } return ret; } RESULT sortByNumber() { RESULT ret = {}; int i = 0; for (auto it = Number.begin(); it != Number.end(); it++) { if (i == 5) break; mstrcpy(ret.mApp[i], (*it)->nameApp.c_str()); i++; } return ret; } // #ifndef _CRT_SECURE_NO_WARNINGS #define _CRT_SECURE_NO_WARNINGS #endif #include <stdio.h> static int mstrcmp(const char str1[], const char str2[]) { int c = 0; while (str1[c] != 0 && str1[c] == str2[c]) ++c; return str1[c] - str2[c]; } static void mstrcpy(char dest[], const char src[]) { int i = 0; while (src[i] != '\0') { dest[i] = src[i]; i++; } dest[i] = src[i]; } static const int CMD_INIT = 100; static const int CMD_ADDRATING = 200; static const int CMD_DELETERATING = 300; static const int CMD_BANUSER = 400; static const int CMD_SORTBYSCORE = 500; static const int CMD_SORTBYNUMBER = 600; static const int MAXL = 16; struct RESULT { char mApp[5][MAXL]; }; extern void init(int, const char[][MAXL]); extern void addRating(int, const char[MAXL], int); extern void deleteRating(int, const char[MAXL]); extern void banUser(int); extern RESULT sortByScore(); extern RESULT sortByNumber(); static char applist[10000][MAXL]; static int mSeed; static char anslist[10000][MAXL]; static int pseudoRand() { mSeed = (mSeed * 214013 + 2531011) & 0xFFFFFFFF; return (mSeed >> 16) & 0x7FFF; } static void makeApp(int num) { for (int i = 0; i < num; i++) { int len = 5 + pseudoRand() % 11; for (int j = 0; j < len; j++) { applist[i][j] = 'A' + pseudoRand() % 26; } applist[i][len] = 0; } } static int run(void) { int ret = 0; int query_cnt, cmd; int appNum; int mUser, mApp, mScore; RESULT user; int ans; scanf("%d %d %d", &query_cnt, &mSeed, &appNum); makeApp(appNum); for (int i = 0; i < appNum; i++) mstrcpy(anslist[i], applist[i]); for (int q = 0; q < query_cnt; q++) { scanf("%d", &cmd); switch (cmd) { case CMD_INIT: init(appNum, applist); ret = 1; break; case CMD_ADDRATING: scanf("%d %d %d", &mUser, &mApp, &mScore); addRating(mUser, applist[mApp], mScore); break; case CMD_DELETERATING: scanf("%d %d", &mUser, &mApp); deleteRating(mUser, applist[mApp]); break; case CMD_BANUSER: scanf("%d", &mUser); banUser(mUser); break; case CMD_SORTBYSCORE: user = sortByScore(); for (int i = 0; i < 5; i++) { scanf("%d", &ans); if (mstrcmp(user.mApp[i], anslist[ans])) ret = 0; } break; case CMD_SORTBYNUMBER: user = sortByNumber(); for (int i = 0; i < 5; i++) { scanf("%d", &ans); if (mstrcmp(user.mApp[i], anslist[ans])) ret = 0; } break; default: ret = 0; break; } } return ret; } int main() { setbuf(stdout, NULL); freopen("input.txt", "r", stdin); int tc, MARK; scanf("%d %d", &tc, &MARK); for (int t = 1; t <= tc; t++) { int score = run() ? MARK : 0; printf("#%d %d\n", t, score); } return 0; }
Editor is loading...
Leave a Comment