Untitled

 avatar
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