Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
5.4 kB
2
Indexable
Never
--------------------MAIN---------------------

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>

#define ADDNEWS (100)
#define ERASENEWS (200)
#define READNEWS (300)
#define CHANGESECTION (400)
#define GETLIST (500)

extern void init();
extern void addNews(int mSection, int mNewsId);
extern void eraseNews(int mNewsId);
extern void readNews(int mUserId, int mNewsId);
extern void changeSection(int mNewsId, int mSection);
extern int getList(int mUserId, int mList[]);

/////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////

static int run()
{
	int N;
	int cmd;
	int mSection, mUserId;
	int mNewsId;
	int res[10];

	init();

	int retVal = 1;

	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf("%d", &cmd);
		switch (cmd)
		{
		case ADDNEWS:
			scanf("%d %d", &mSection, &mNewsId);
			addNews(mSection, mNewsId);
			break;
		case ERASENEWS:
			scanf("%d", &mNewsId);
			eraseNews(mNewsId);
			break;
		case READNEWS:
			scanf("%d %d", &mUserId, &mNewsId);
			readNews(mUserId, mNewsId);
			break;
		case CHANGESECTION:
			scanf("%d %d", &mNewsId, &mSection);
			changeSection(mNewsId, mSection);
			break;
		case GETLIST:
			scanf("%d", &mUserId);
			int num = getList(mUserId, res);
			int numans;
			scanf("%d", &numans);
			if (numans != num)
				retVal = 0;

			for (int j = 0; j < numans; j++) {
				int ans;
				scanf("%d", &ans);
				if (ans != res[j])
					retVal = 0;
			}
			break;
		}
	}

	return retVal;
}

int main()
{
	setbuf(stdout, NULL);
	freopen("input.txt", "r", stdin);

	int T, MARK;

	scanf("%d %d", &T, &MARK);

	for (int tc = 1; tc <= T; tc++) { 
		int score = run() ? MARK : 0;
		printf("#%d %d\n", tc, score);
	}

	return 0;
}


-------------------------USER---------------------------

#include <queue>
#include <vector>
#define USER 100001
#define NEWS 50001
#define HASH_SIZE 105001
#define SECTION 10
#define swap(x,y) if (x!=y) x ^= y ^= x ^= y

using namespace std;

struct NewsData{
	int score;
	int section;
	bool isErase;
};

struct News{
	int id;
	int score;
};

//News map[SECTION][NEWS];

//struct comparator{
//	inline bool operator()(const News& news1, const News& news2){
//		if(news1.score == news2.score){
//			if(news1.cntRead != news2.cntRead ){
//				return news1.cntRead < news2.cntRead;
//			}
//			return news1.id < news2.id;
//		}
//		else
//			return news1.score < news2.score;
//};



struct Heap{
	News news[HASH_SIZE];
	int size;

	bool compare(int first, int second){
		if(news[first].score > news[second].score || news[first].score == news[second].score && news[first].id > news[second].id)
			return true;
		return false;
	}

	void push(int id, int score){
		news[size].id = id;
		int child = size;
		int parent  = (size - 1)/2;
		while(parent >= 0){
			if(compare(child, parent)){
				swap(news[child].id, news[parent].id);
				swap(news[child].score, news[parent].score);
				child  = parent;
				parent = (size - 1)/2;
			}
			else break;
		}
		size++;
	}
	News pop(){
		News result;
		result.id = 0;
		if(size == 0) return result;
		result = news[0];
		news[0] = news[size--];
		int parent = 0;
		int left = 2*parent + 1;
		int right = 2*parent + 2;
		int replace = -1;
		while(left <= size){
			if(right <= size){
				if(compare(left,right)){
					if(compare(left, parent)){
						replace = left;
					}
				}
				else{
					if(compare(right, parent)){
						replace = right;
					}
				}
			}
			else{
				if(compare(left, parent)){
					replace = left;
				}
			}
			if(replace != -1){
				swap(news[replace].id, news[parent].id);
				swap(news[replace].score, news[parent].score);
				parent = replace;
				left = 2 * parent  + 1;
				right = left  + 1;
				replace  = -1;
			}
			else break;
		}

		return result;
	}
};

NewsData newsData[NEWS];
int interested[USER];
Heap heap[11];

void init()
{
	for(int i = 0; i < 11; i++){
		heap[i].size = 0;
	}
	for(int i = 0; i < USER; i++){
		interested[i] = 10;
	}
}

void addNews(int mSection, int mNewsId)
{
	for(int i = 0; i < 11; i++){
		heap[i].push(mNewsId, (mSection == i)? 10 : 0);
	}
	newsData[mNewsId].section = mSection;
	newsData[mNewsId].score = 0;
}

void eraseNews(int mNewsId)
{
	newsData[mNewsId].isErase = true;
}

void readNews(int mUserId, int mNewsId)
{
	for(int i = 0; i < 11; i++){
		heap[i].push(mNewsId, (newsData[mNewsId].section == i)? (newsData[mNewsId].score + 10): newsData[mNewsId].score);
	}
	interested[mUserId] = newsData[mNewsId].section;
}

void changeSection(int mNewsId, int mSection)
{
	int old_section = newsData[mNewsId].section;
	heap[old_section].push(mNewsId, newsData[mNewsId].score);
	heap[mSection].push(mNewsId, newsData[mNewsId].score + 10);
	newsData[mNewsId].section  = mSection;
}

int getList(int mUserId, int mList[])
{
	int result = 0;
	int section = interested[mUserId];
	while(result < 10){
		News news = heap[section].pop();
		if(news.id == 0) break;
		int newId = news.id;
		int score = news.score;
		if(!newsData[newId].isErase 
			&& (newsData[newId].section != section && newsData[newId].score == score)
			|| (newsData[newId].section == section && newsData[newId].score + 10 == score)){
				mList[result] = newId;
				result++;
		}
	}

	for(int i = 0; i < 10; i++){
		int newId = mList[i];
		heap[section].push(newId, (newsData[newId].section == section)? newsData[newId].score + 10 : newsData[newId].score );

	}

	return result;
}