#include <iostream>
#include <unordered_map>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
using namespace std;

/*
Write a game leader board. Record user id and game score. Return top n players.
*/

struct UserWithScore {
	string user_id;
	int score;
	UserWithScore(string user_id_, int score_): user_id(user_id_), score(score_) {}
};

struct Compare {
	bool operator()(UserWithScore a, UserWithScore b) {
		return a.score > b.score;
	}
};

class GameLeaderBoard {
public:
	unordered_map<string,int> ht;
		
	void add_score(string user_id, int game_score) {
		auto it = ht.find(user_id);
		if (it == ht.end()) {
			ht.insert(make_pair(user_id, game_score));
		} else {
			if (game_score > it->second) {
				it->second = game_score;
			}
		}
	}
	
	vector<UserWithScore> get_top_n(int n) {
		vector<UserWithScore> out;
		
		priority_queue<UserWithScore, std::vector<UserWithScore>, Compare> min_heap;
		
		for (auto e : ht) {
			if (min_heap.size() < n) {
				min_heap.push(UserWithScore(e.first, e.second));
			} else {
				auto it = min_heap.top();
				if (it.score < e.second) {
					min_heap.pop();
					min_heap.push(UserWithScore(e.first, e.second));
				}
			}
		}
		
		while (!min_heap.empty()) {
			auto n = min_heap.top();
			min_heap.pop();
			out.push_back(n);
		}
		
		return out;
	}
};

void print(vector<UserWithScore> top_n) {
	for (int i = 0; i < top_n.size(); i++) {
		cout << "user: " << top_n[i].user_id << ", score: " << top_n[i].score << endl;
	}
	cout << '\n';
}

int main() {
	// your code goes here
	
	GameLeaderBoard g1;
	g1.add_score("gerald", 10);
	g1.add_score("tushar", 20);
	g1.add_score("gaurav", 15);
	g1.add_score("vishal", 3);
	print(g1.get_top_n(3));
	
	g1.add_score("gerald", 30);
	print(g1.get_top_n(3));
	
	return 0;
}