0355.cpp (1382B)
1 class Twitter { 2 vector<pair<int, int>> posts[501]; 3 bool following[501][501] = {0}; 4 int time = 0; 5 6 public: 7 Twitter() { 8 for (int i = 0; i <= 500; i++) { 9 following[i][i] = true; 10 } 11 } 12 13 void postTweet(int userId, int tweetId) { posts[userId].emplace_back(time++, tweetId); } 14 15 vector<int> getNewsFeed(int userId) { 16 using type_t = tuple<int, int, int>; 17 static const auto cmp = [](const type_t &a, const type_t &b) { return get<0>(a) < get<0>(b); }; 18 priority_queue<type_t, vector<type_t>, decltype(cmp)> pq(cmp); 19 20 for (int i = 0; i <= 500; i++) { 21 if (!following[userId][i]) continue; 22 23 const int n = size(posts[i]); 24 if (n == 0) continue; 25 26 pq.emplace(posts[i][n - 1].first, i, n - 1); 27 if (size(pq) > 10) pq.pop(); 28 } 29 30 vector<int> res; 31 while (!pq.empty() && size(res) < 10) { 32 const auto [time, user, idx] = pq.top(); 33 pq.pop(); 34 res.push_back(posts[user][idx].second); 35 if (idx - 1 >= 0) pq.emplace(posts[user][idx - 1].first, user, idx - 1); 36 } 37 38 return res; 39 } 40 41 void follow(int followerId, int followeeId) { following[followerId][followeeId] = true; } 42 43 void unfollow(int followerId, int followeeId) { following[followerId][followeeId] = false; } 44 };