Rang lista

Napisati generičku klasu rang_lista<T> koja održava rang listu igrača tipa T na osnovu njihovih skorova. Klasa treba da podržava sledeće operacije:

Prva operacija treba da bude složenosti ne veće od $O(\log n)$, a druga operacija treba da bude složenosti ne veće od $O(k)$.

Ulaz

Sa standardnog ulaza se učitavaju celi brojevi $n$, $m$ i $k$, gde je $n$ broj igrača, $m$ broj ažuriranja skora, a $k$ broj igrača koje treba ispisati iz rang liste.

Zatim se učitavaju $n$ igraca, gde svaki igrač predstavljen pomoću svog imena (string bez razmaka) i države (string bez razmaka) odakle dolazi.

Nakon toga odvija se $m$ nasumičnih ažuriranja skora (sa poenima od 0 do 100) za tačno 10 igrača. Za početno seme uzeti broj 42.

Izlaz

Za svaku od $m$ ažuriranja skora, na standardni izlaz ispisati prvih $k$ igrača sa najvišim skorovima, u opadajućem redosledu.

Primer

stdin

5 3 3
Novak Srbija
Anton Hrvatska
Slavko Bosna
Njegoslav CrnaGora
Slavoj Slovenija

stdout

-------------------------
Njegoslav iz CrnaGora sa skorom 213
Slavoj iz Slovenija sa skorom 115
Slavko iz Bosna sa skorom 96
-------------------------
Slavoj iz Slovenija sa skorom 227
Njegoslav iz CrnaGora sa skorom 222
Slavko iz Bosna sa skorom 196
-------------------------
Njegoslav iz CrnaGora sa skorom 402
Slavoj iz Slovenija sa skorom 340
Slavko iz Bosna sa skorom 261
-------------------------

Rešenje

main.cpp

#include <iostream>
#include <set>
#include <unordered_map>
#include <random>

namespace matf
{
	/* Klasa za rang listu */
	template <typename T>
	class rang_lista
	{
		typedef typename std::pair<size_t, T> Par;

		public:
			/* Azurira skor igraca za dati iznos */
			void azuriraj_skor(T igrac, size_t novi_skor)
			{
				// Ako igrac vec postoji, ukloni ga iz ranga
				auto it = skor.find(igrac);
				if (it != skor.end()) {
					size_t stari_skor = it->second;
					rang.erase({stari_skor, igrac});
				}

				// Azuriraj skor igraca
				skor[igrac] += novi_skor;

				// Dodaj igraca u rang
				rang.insert({skor[igrac], igrac});
			}

			/* Najboljih k igraca */
			void top_k_igraca(size_t k)
			{
				for (auto it = rang.begin(); it != rang.end() && k > 0; ++it, --k) {
					std::cout << it->second << " sa skorom " << it->first << std::endl;
				}
			}

		private:
			std::unordered_map<T, size_t> skor;
			std::set<Par, std::greater<Par>> rang;
	};
};

struct Igrac {
	std::string ime;
	std::string drzava;
};

std::ostream& operator<<(std::ostream& os, const Igrac* igrac) {
	return os << igrac->ime << " iz " << igrac->drzava;
}

int main(void)
{
	srand(42);

	int n, m, k; std::cin >> n >> m >> k;

	std::vector<Igrac*> igraci;
	matf::rang_lista<Igrac*> rl;

	while (n--) {
		std::string ime, drzava;
		std::cin >> ime >> drzava;

		Igrac* igrac = new Igrac{ime, drzava};
		igraci.push_back(igrac);
		rl.azuriraj_skor(igrac, 0);
	}

	while (m--) {
		for (int i = 0; i < 10; ++i) {
			size_t poeni = rand() % 100;
			Igrac *igrac = igraci[rand() % igraci.size()];

			rl.azuriraj_skor(igrac, poeni);
		}

		std::cout << "-------------------------" << std::endl;
		rl.top_k_igraca(k);
	}
	std::cout << "-------------------------" << std::endl;

	for (Igrac* igrac : igraci) {
		delete igrac;
	}

	return 0;
}