Untitled
#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