Power Walking (Codeforces 1642B)
Tags: Greedy, greedy

Sam is a kindergartener, and there are $$$n$$$ children in his group. He decided to create a team with some of his children to play "brawl:go 2".Sam has $$$n$$$ power-ups, the $$$i$$$-th has type $$$a_i$$$. A child's strength is equal to the number of different types among power-ups he has.For a team of size $$$k$$$, Sam will distribute all $$$n$$$ power-ups to $$$k$$$ children in such a way that each of the $$$k$$$ children receives at least one power-up, and each power-up is given to someone.For each integer $$$k$$$ from $$$1$$$ to $$$n$$$, find the minimum sum of strengths of a team of $$$k$$$ children Sam can get.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 3 \cdot 10^5$$$) — the number of test cases. Description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$). The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — types of Sam's power-ups.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output: For every test case print $$$n$$$ integers.The $$$k$$$-th integer should be equal to the minimum sum of strengths of children in the team of size $$$k$$$ that Sam can get.

Note: One of the ways to give power-ups to minimise the sum of strengths in the first test case:   $$$k = 1: \{1, 1, 2\}$$$    $$$k = 2: \{1, 1\}, \{2\}$$$    $$$k = 3: \{1\}, \{1\}, \{2\}$$$   One of the ways to give power-ups to minimise the sum of strengths in the second test case:   $$$k = 1: \{1, 2, 2, 2, 4, 5\}$$$    $$$k = 2: \{2, 2, 2, 4, 5\}, \{1\}$$$    $$$k = 3: \{2, 2, 2, 5\}, \{1\}, \{4\}$$$    $$$k = 4: \{2, 2, 2\}, \{1\}, \{4\}, \{5\}$$$    $$$k = 5: \{2, 2\}, \{1\}, \{2\}, \{4\}, \{5\}$$$    $$$k = 6: \{1\}, \{2\}, \{2\}, \{2\}, \{4\}, \{5\}$$$   

Sample Inputs:
2
3
1 1 2
6
5 1 2 2 2 4

Sample Outputs:
2 2 3 
4 4 4 4 5 6

Solution (Python):
from enum import Enum, auto
import copy
import sys
input = sys.stdin.readline

def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        x = len(set(a))
        res = []
        for i in range(n):
            res.append(x if i < x else i + 1)
        print(' '.join(list(map(str, res))))
main()

Solution (Python):
for s in [*open(0)][2::2]:
    a = s.split()
    m = len({*a})
    print(*(max(m, i + 1) for i in range(len(a))))

Solution (Python):
import bisect
import collections
import sys
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.buffer.readline())

def MI():
    return map(int, sys.stdin.buffer.readline().split())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def BI():
    return sys.stdin.buffer.readline().rstrip()

def SI():
    return sys.stdin.buffer.readline().rstrip().decode()

def li():
    return [int(i) for i in input().split()]

def lli(rows):
    return [li() for _ in range(rows)]

def si():
    return input()

def ii():
    return int(input())

def ins():
    return input().split()

def drank(d, processing, da, rank):
    tmp = 10 ** 9
    if len(d[da]) == 1:
        return 1
    for di in d[da]:
        if processing[di - 1] == 0:
            processing[di - 1] = 1
            tmp = min(tmp, drank(d, processing, di, rank))
            processing[di - 1] = 0
    rank[da - 1] = tmp + 1
    return tmp + 1

def binary_search(n, a):
    l = len(a)
    low = 0
    high = l - 1
    while high >= low:
        mid = (high + low) // 2
        if a[mid] == n:
            return mid
        elif a[mid] > n:
            high = mid - 1
        else:
            low = mid + 1
    return -1
mod = 10 ** 9 + 7

def solve():
    n = II()
    l = len(set(LI()))
    return ' '.join([str(max(i + 1, l)) for i in range(n)])

def main():
    for _ in range(II()):
        sys.stdout.write(str(solve()) + '\n')
if __name__ == '__main__':
    main()