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
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

// Clean O(n) solution

int main() {
	std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);
	int n;
	std::cin >> n;
	std::vector<int> input(n+1);
	for (int i = 0; i < n; ++i) {
		std::cin >> input[i];
	}
	input[n] = INT_MAX;
	std::sort(input.begin(), input.end());
	std::vector<int> A;
	int prev = input[0];
	int cnt = 1;
	for (int i = 1; i <= n; ++i) {
		if (input[i] == prev) {
			cnt++;
		} else {
			A.push_back(cnt);
			prev = input[i];
			cnt = 1;
		}
	}
	int N = A.size();
//	std::cout << "A[]:";
//	for (int i = 0; i < N; ++i) {
//		std::cout << ' ' << A[i];
//	}
//	std::cout << '\n';
	std::vector<int> answers(n+1);
	for (int i = 0; i < N; ++i) {
		// for (int d = (A[i]+1)/2; d >= )
		for (int d = 1; d <= A[i]; ++d) {
			answers[d] += A[i] / d * d;
		}
	}
	for (int k = 1; k <= n; ++k) {
		std::cout << answers[k] << ' ';
	}
	std::cout << '\n';
}