Problem:


Score : 600 points

Problem Statement

Takahashi has N cards. The i-th of these cards has an integer A_i written on it.

Takahashi will choose an integer K, and then repeat the following operation some number of times:

Choose exactly K cards such that the integers written on them are all different, and eat those cards. (The eaten cards disappear.)

For each K = 1,2, \ldots, N, find the maximum number of times Takahashi can do the operation.

Constraints

 1 \le N \le 3 \times 10^5 

 1 \le A_i \le N 

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Print N integers.
The t-th (1 \le t \le N) of them should be the answer for the case K=t.

Sample Input 1

3
2 1 2

Sample Output 1

3
1
0

For K = 1, we can do the operation as follows:

Choose the first card to eat.

Choose the second card to eat.

Choose the third card to eat.

For K = 2, we can do the operation as follows:

Choose the first and second cards to eat.

For K = 3, we cannot do the operation at all. Note that we cannot choose the first and third cards at the same time.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

5
2
1
1
1

Sample Input 3

4
1 3 3 3

Sample Output 3

4
1
0
0



Sample input:
3
2 1 2


Sample output:
3
1
0

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
from bisect import bisect_left

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    aa = list(Counter(aa).values())
    aa.sort()
    # print(aa)
    r0 = sum(aa) + 1
    for k in range(1, n + 1):
        l = 0
        r = r0
        while l + 1 < r:
            m = (l + r) // 2
            i = bisect_left(aa, m)
            s = sum(aa[:i]) + m * (len(aa) - i)
            if s >= m * k:
                l = m
            else:
                r = m
        print(l)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

from collections import Counter
from copy import deepcopy
from bisect import insort


def main():
    n = int(input())
    a = list(map(int, input().split()))

    #n = 3 * 10 ** 5
    #a = list(range(1, n + 1))

    c = Counter(a)
    c = list(c.values())
    c.sort()

    k_mx = len(c)

    for k in range(1, n + 1):
        if k > k_mx:
            print(0)
            continue

        cp = deepcopy(c)
        ans = 0

        while True:
            eat = cp[-k:]
            if eat[0] == 0:
                break

            cp = cp[:-k]
            for e in eat:
                left = e - eat[0]
                insort(cp, left)

            ans += eat[0]

        print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

from collections import Counter
from heapq import heapify, heappush, heappop
from copy import deepcopy


def main():
    n = int(input())
    a = list(map(int, input().split()))

    #n = 3 * 10 ** 5
    #a = list(range(1, n + 1))

    c = Counter(a)
    c = [-e for e in c.values()]
    heapify(c)

    k_mx = len(c)

    for k in range(1, n + 1):
        if k > k_mx:
            print(0)
            continue

        ans = -1
        mn = -1
        cp = deepcopy(c)
        end = False
        while not end:
            ans -= mn
            eat = []
            for _ in range(k):
                mn = heappop(cp)
                if mn >= 0:
                    end = True
                    break
                eat.append(mn)

            for e in eat:
                heappush(cp, e - mn)

        print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

from collections import Counter
from heapq import heapify, heappush, heappop
from copy import deepcopy


def main():
    n = int(input())
    a = list(map(int, input().split()))

    c = Counter(a)
    c = [-e for e in c.values()]
    heapify(c)

    k_mx = len(c)

    for k in range(1, n + 1):
        if k > k_mx:
            print(0)
            continue

        ans = -1
        cp = deepcopy(c)
        end = False
        while not end:
            ans += 1
            eat = []
            for _ in range(k):
                mn = heappop(cp)
                if mn == 0:
                    end = True
                    break
                eat.append(mn + 1)

            for e in eat:
                heappush(cp, e)

        print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections

def solve(N: int, A: "List[int]"):
    counter = sorted(list(collections.Counter(A).values()),reverse=True)
    for i in range(1,N+1):
        if len(counter)<i:
            print(0)
            continue
        c_index = 0
        n = N
        k = i 
        while counter[c_index]*k > n and c_index<len(counter)-1:
            n-=counter[c_index]
            c_index+=1
            k-=1
        print(n//k)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections
import copy
def dellist(items, indexes):
    for index in sorted(indexes, reverse=True):
        del items[index]


def max_fetch(k,c,N):
    if c[0]*k <= N:
        return N//k
    else:
        return max_fetch(k-1,c[1:],N-c[0])



def solve(N: int, A: "List[int]"):
    counter = sorted(list(collections.Counter(A).values()),reverse=True)
    for i in range(1,N+1):
        if len(counter) < i:
            print(0)
            continue
        if counter[0]*i <= N:
            print(N//i)
            continue

        print(max_fetch(i,counter,N))
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections
import copy
def dellist(items, indexes):
    for index in sorted(indexes, reverse=True):
        del items[index]

def solve(N: int, A: "List[int]"):
    counter = sorted(list(collections.Counter(A).values()),reverse=True)
    for i in range(1,N+1):
        if len(counter) < i:
            print(0)
            continue
        if counter[0]*i <= N:
            print(N//i)
            continue
        c = copy.deepcopy(counter)
        answer = 0
        while c:
            if len(c) < i:
                break
            remove_index = []
            for j in range(i):
                c[j]-=1
                if c[j] == 0:
                    remove_index.append(j)
            if remove_index:
                dellist(c,remove_index)
            answer += 1

        print(answer)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N=int(input())
A=list(map(int,input().split()))
C=list(Counter(A).values())
C.sort()

def ans(C,k):
    if C==[]:
        return 0
    elif sum(C)>=k*C[-1]:
        return sum(C)//k
    else:
        return ans(C[:-1],k-1)


for k in range(1,N+1):
    print(ans(C,k))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections
import copy
def dellist(items, indexes):
    for index in sorted(indexes, reverse=True):
        del items[index]

def solve(N: int, A: "List[int]"):
    counter = sorted(list(collections.Counter(A).values()),reverse=True)
    for i in range(1,N+1):
        if len(counter) < i:
            print(0)
            continue
        c = copy.deepcopy(counter)
        answer = 0
        while c:
            if len(c) < i:
                break
            remove_index = []
            for j in range(i):
                c[j]-=1
                if c[j] == 0:
                    remove_index.append(j)
            if remove_index:
                dellist(c,remove_index)
            answer += 1

        print(answer)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections
import copy
def dellist(items, indexes):
    for index in sorted(indexes, reverse=True):
        del items[index]

def solve(N: int, A: "List[int]"):
    counter = sorted(list(collections.Counter(A).values()),reverse=True)
    for i in range(1,N+1):
        c = copy.deepcopy(counter)
        answer = 0
        while c:
            if len(c) < i:
                break
            remove_index = []
            for j in range(i):
                c[j]-=1
                if c[j] == 0:
                    remove_index.append(j)
            if remove_index:
                dellist(c,remove_index)
            answer += 1

        print(answer)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from bisect import bisect_left

N = int(input())
A = list(map(int, input().split()))
a = list(Counter(A).values())
a.sort()
s = sum(a)

for i in range(1, N + 1):
    if i == 1:
        print(s)
    elif len(a) < i:
        print(0)
    else:
        n = s // i
        for j in reversed(range(1, n + 1)):
            t = bisect_left(a, j)
            if j * i <= sum(a[:t]) + (len(a) - t) * j:
                print(j)
                break