1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <unordered_map>
#include <vector>

int main()
{
	int l_zn; std::cin >> l_zn;

	std::unordered_map< int, int > miasta;

	for (int i = 0; i < l_zn; ++i) {
		int miasto; std::cin >> miasto;
		miasta[miasto] += 1;
	}

	std::vector< int > licznosci;
	auto get_value = [](std::pair< int, int > const& p) { return p.second; };
	std::transform(miasta.begin(), miasta.end(), std::back_inserter(licznosci), get_value);

	// zgubilem numery miast, mam tylko informacje, ile bylo znaczkow z danego miasta
	// 1, 1, 2 (miasto z jednym znaczkiem, kolejne miasto z jednym znaczkiem, miasto z dwoma znaczkami)

	std::sort(licznosci.begin(), licznosci.end());

	std::vector< int >odp(l_zn);
	odp[0] = l_zn;

	auto it = licznosci.begin();
	auto et = licznosci.end();
	int odrzut = 0;
	for (int i = 1; i < l_zn; ++i ) {
		int zgloszeni = i + 1;
		auto jt = std::lower_bound(it, et, zgloszeni);

		odrzut += std::accumulate(it, jt, 0);
		odp[i] = l_zn - odrzut;

		for (auto kt = jt; kt != et; ++kt) {
			odp[i] -= (*kt % zgloszeni);
		}

		it = jt;
	}

	for (int i = 0; i < l_zn - 1; ++i) {
		std::cout << odp[i] << " ";
	}
	std::cout << odp[l_zn - 1] << "\n";
}