Untitled

mail@pastecode.io avatar
unknown
plain_text
20 days ago
7.6 kB
4
Indexable
Never
#include <set>
#include <vector>
#include <list>
#define MAX 100011
using namespace std;
  
 
struct POST{
    int nlike;
    int time;
    int Long;
    int uid;
} post[MAX];
int rearID,frontID; 
int Total_user;
list <int> top_10_Old[1011];
int isFrend[1001][1001];
 
struct CMP{
    bool operator()(int i, int j){//idx of post
        if(post[i].Long <= 1000 && post[j].Long <= 1000){// new
            if(post[i].nlike != post[j].nlike) return post[i].nlike > post[j].nlike;
            else (post[i].time > post[j].time);
        }
         
        return (post[i].time > post[j].time);//old
    }
};
  
void init(int n){
    for(register int i = 1; i <= n; i++){
        for(register int j = 1; j <= n; j++) isFrend[i][j] = 0;
        isFrend[i][i] = 1;
    }
    for (int i = 0; i <1010 ; i++)
    {
        top_10_Old[i].clear();
    }
    rearID = frontID=0;
    Total_user=n;
}
  
void follow(int u1, int u2, int time){
    isFrend[u1][u2] = 1;
}
  
void makePost(int uid, int pid, int time){
    post[pid].time = time;
    post[pid].nlike = 0;
    post[pid].Long = 0;
    post[pid].uid = uid;
    rearID++;
}
  
void like(int pid, int time){
    post[pid].nlike++;
}
 
 
void getFeed(int uid, int timestamp, int pidList[])
{
    if(rearID != 0){
        for (;timestamp-post[frontID+1].time>1000 && frontID < rearID; frontID++)
        {
            post[frontID+1].Long = timestamp-post[frontID+1].time;
            int curr_id= post[frontID+1].uid;
            top_10_Old[curr_id].push_front(frontID+1);
        }
        set <int, CMP> output ;
        for (int i = frontID+1; i <=rearID ; i++)
        {
            if (isFrend[uid][post[i].uid])
                output.insert(i);
        }
 
        int remaining = 10 - output.size();
 
        if (remaining >0)
        {
            for (int user_id = 1; user_id <= Total_user; user_id++)
            {
                if (isFrend[uid][user_id])
                {
                    int i = 1;
                    for(auto it = top_10_Old[user_id].begin(); it !=  top_10_Old[user_id].end() && i <= remaining; it++, i++){
                        output.insert(*it);
                    }
                }
            }
        }
        int i = 0;
        for(auto it = output.begin(); it != output.end() && i < 10; it++, i++)
            pidList[i] = *it;
    }
}
/* 
void init(int N)

A function called once in the beginning of each test case for initialization.

 

Parameters

N: Number of users (2 ≤ N ≤ 1,000)

void follow(int uID1, int uID2, int timestamp)

A function used to make the user “uID1” “follow” the user “uID2”.

A function used to show the posts of the user “uID2” to the user “uID1”.


 

Parameters

uID1, uID2 : User ID (1 ≤ uID1, uID2 ≤ N)

timestamp : Timestamp indicating the current time         

(1 ≤ timestamp ≤ 100,000)

void makePost(int uID, int pID, int timestamp)

A function used to allow the user “uID” to upload the post “pID”.

 

Parameters

uID : User ID (1 ≤ uID ≤ N)

pID : Post ID ( given in ascending order from 1 )

timestamp : Timestamp indicating the current time          

(1 ≤ timestamp ≤ 100,000)

void like(int pID, int timestamp)

A function that adds a “like” to the post “pID”.

As for “pID”, only the value delivered by makePost() is given.

 

Parameters

pID : pID of the post to which a “like” is to be added

timestamp : Timestamp indicating the current time 

(1 ≤ timestamp ≤ 100,000)

void getFeed(int uID, int timestamp, int pIDList[])

A function that finds the “pIDs” of up to 10 posts shown to the user “uID” based on the current “timestamps” to store and return them in descending order of priority in the “pIDList[]” array.

 

Parameters

uID : User ID (1 ≤ uID ≤ N)

timestamp : Timestamp indicating the current time

pIDList[] : Array storing the pIDs of the posts displayed
*/
/*
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include<stdio.h>

extern void init(int N);
extern void follow(int uId1, int uId2, int timestamp);
extern void makePost(int uId, int pId, int timestamp);
extern void like(int pId, int timestamp);
extern void getFeed(int uId, int timestamp, int pIdList[]);

static int mSeed;
static int pseudo_rand(void)
{
	mSeed = mSeed * 431345 + 2531999;
	return mSeed & 0x7FFFFFFF;
}

static int follow_status[1005][1005];
static int answer_score;
static int n; // n >= 2 && n <= 1000
static int end_timestamp;
static int follow_ratio; // follow_ratio >= 1 && follow_ratio <= 10000
static int make_ratio; // make_ratio >= 1 && make_ratio <= 10000
static int like_ratio; // like_ratio >= 1 && like_ratio <= 10000
static int get_feed_ratio; // get_feed_ratio >= 1 && get_feed_ratio <= 10000
static int post_arr[200000];
static int total_post_cnt;
static int min_post_cnt;

static bool run()
{
	int uId1, uId2, pId, pIdList[10], ans_pIdList[10], rand_val;
	bool ret = true;

	scanf("%d%d%d%d%d%d%d", &mSeed, &n, &end_timestamp, &follow_ratio, &make_ratio, &like_ratio, &get_feed_ratio);
	init(n);

	for (int uId1 = 1; uId1 <= n; uId1++)
	{
		follow_status[uId1][uId1] = 1;
		int m = n / 10 + 1;
		if (m > 10)
			m = 10;
		for (int i = 0; i < m; i++)
		{
			uId2 = uId1;
			while (follow_status[uId1][uId2] == 1)
			{
				uId2 = pseudo_rand() % n + 1;
			}
			follow(uId1, uId2, 1);
			follow_status[uId1][uId2] = 1;
		}
	}
	min_post_cnt = total_post_cnt = 1;

	for (int timestamp = 1; timestamp <= end_timestamp; timestamp++)
	{
		rand_val = pseudo_rand() % 10000;
		if (rand_val < follow_ratio)
		{
			uId1 = pseudo_rand() % n + 1;
			uId2 = pseudo_rand() % n + 1;
			int lim = 0;
			while (follow_status[uId1][uId2] == 1 || uId1 == uId2)
			{
				uId2 = pseudo_rand() % n + 1;
				lim++;
				if (lim >= 5)
					break;
			}
			if (follow_status[uId1][uId2] == 0)
			{
				follow(uId1, uId2, timestamp);
				follow_status[uId1][uId2] = 1;
			}
		}
		rand_val = pseudo_rand() % 10000;

		if (rand_val < make_ratio)
		{
			uId1 = pseudo_rand() % n + 1;
			post_arr[total_post_cnt] = timestamp;

			makePost(uId1, total_post_cnt, timestamp);
			total_post_cnt += 1;
		}

		rand_val = pseudo_rand() % 10000;

		if (rand_val < like_ratio && total_post_cnt - min_post_cnt > 0)
		{
			while (post_arr[min_post_cnt] < timestamp - 1000 && min_post_cnt < total_post_cnt)
				min_post_cnt++;

			if (total_post_cnt != min_post_cnt)
			{
				pId = pseudo_rand() % (total_post_cnt - min_post_cnt) + min_post_cnt;
				like(pId, timestamp);
			}
		}

		rand_val = pseudo_rand() % 10000;
		if (rand_val < get_feed_ratio && total_post_cnt > 0)
		{
			uId1 = pseudo_rand() % n + 1;
			getFeed(uId1, timestamp, pIdList);

			for (int i = 0; i < 10; i++)
			{
				scanf("%d", ans_pIdList + i);
			}

			for (int i = 0; i < 10; i++)
			{
				if (ans_pIdList[i] == 0)
					break;

				if (ans_pIdList[i] != pIdList[i])
				{
					ret = false;
				}
			}
		}
	}

	return ret;
}

int main()
{
//	freopen("sample_input.txt", "r", stdin);
	setbuf(stdout, NULL);
	int tc;
	scanf("%d%d", &tc, &answer_score);

	for (int t = 1; t <= tc; t++)
	{
		int score;
		for (int i = 0; i < 1005; i++)
			for (int j = 0; j < 1005; j++)
				follow_status[i][j] = 0;

		if (run())
			score = answer_score;
		else
			score = 0;

		printf("#%d %d\n", t, score);
	}
	return 0;
}

*/
Leave a Comment