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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// PA2024 runda 2A -  https://sio2.mimuw.edu.pl/c/pa-2024-1/p/zna/

//-std=c++20
#include<iostream>
#include <cstddef>
#include<map>
#include <algorithm>
#include<vector>

using I = u_int64_t;


struct Zna {
    I n; // stamps <=300K
    std::map<I, I> city_counts;
    std::vector<I> counts;
    I sum = 0;

    void run() {
        std::cin >> n;
        for (int i = 0; i < n; ++i) {
            next_stamp();
        }
        counts.resize(n, 0);
        I i = 0;
        for (const auto &pair: city_counts) {
            counts[i++] = pair.second;
            sum += pair.second;
        }
        std::sort(counts.begin(), counts.end());
        // one buyer
        std::cout << sum;
        I smallest_city = 0; // counter for counts
        for (I buyers = 2; buyers <= n; buyers++) {
            //find count at least buyers
            while (smallest_city < counts.size() && counts[smallest_city] < buyers) {
                sum -= counts[smallest_city];
                smallest_city++;
            }
            I reminders = 0;
            for (I z = smallest_city; z < counts.size(); z++) {
                reminders += counts[z] % buyers;
            }
            std::cout << " " << (sum - reminders);
        }

    }

    void next_stamp() {
        I a;
        std::cin >> a;
        if (city_counts.contains(a)) {
            city_counts[a]++;
        } else {
            city_counts[a] = 1;
        }

    }




};

//16:20 - 16:50, 17:20-17:25
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    Zna zna;
    zna.run();
}