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: Accepted

Solution code:
from collections import Counter
from itertools import accumulate
import bisect

printRows = lambda x:print('\n'.join(map(str,x)))

n = int(input())
a = list(map(int, input().split()))
b = sorted(Counter(a).values())
exist = len(b)
b = [0]*(n-exist)+b
c = list(accumulate([0]+b))

ans = [n]
for k in range(2,n+1):
    l = 0
    r = n//k+1
    while r-l>1:
        x = (r+l)//2
        i = bisect.bisect_left(b,x)
        if c[i]+(n-i)*x>=x*k:
            l = x
        else:
            r = x
    ans.append(l)

printRows(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import accumulate
import bisect

printRows = lambda x:print('\n'.join(map(str,x)))

n = int(input())
a = list(map(int, input().split()))
b = sorted(Counter(a).values())
exist = len(b)
b = [0]*(n-exist)+b
c = list(accumulate([0]+b))

ans = [n]
for k in range(2,n//2+1):
    if k>exist:
        ans.append(0)
        continue
    l = 0
    r = n//k+1
    while r-l>1:
        x = (r+l)//2
        i = bisect.bisect_left(b,x)
        if c[i]+(n-i)*x>=x*k:
            l = x
        else:
            r = x
    ans.append(l)

for k in range(max(n//2+1,2),n+1):
    if exist>=k:
        ans.append(1)
    else:
        ans.append(0)

printRows(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import accumulate
import bisect

n = int(input())
a = list(map(int, input().split()))
b = sorted(Counter(a).values())
exist = len(b)
b = [0]*(n-exist)+b
c = list(accumulate([0]+b))

print(n)
for k in range(2,n//2+1):
    l = 0
    r = n+1
    while r-l>1:
        x = (r+l)//2
        i = bisect.bisect_left(b,x)
        if c[i]+(n-i)*x>=x*k:
            l = x
        else:
            r = x
    print(l)

for k in range(max(n//2+1,2),n+1):
    if exist>=k:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
readline = sys.stdin.readline

N = int(readline())
A = list(map(int, readline().split()))


table = Counter()
for a in A:
    table[a] += 1

table = list(table.values())
table.sort(reverse = True)
L = len(table)
ata = table[:] + [0]
for i in range(1, L):
    ata[i] += ata[i-1]


vm = [-1]*(N+2)
for med in range(N, 0, -1):
    idx = -1
    for v in range(max(0, vm[med+1]), L):
        if table[v] <= med:
            break
        idx = v
    vm[med] = idx
Ans = [None]*N
for k in range(1, N+1):
    ok = 0
    ng = N//k+1
    while abs(ok-ng) > 1:
        med = (ok+ng)//2
        res = N - ata[vm[med]] + med*(vm[med]+1)
        if res >= k*med:
            ok = med
        else:
            ng = med
    Ans[k-1] = ok
print('\n'.join(map(str, Ans)))

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
c = list(Counter(ai for ai in map(int, input().split())).values())
c.sort()

clen = len(c)

s = [0] * (clen + 1)
for i in range(clen):
    s[i + 1] = s[i] + c[i]

for i in range(1, n + 1):
    rest = clen - i
    if rest < 0:
        print(0)
        continue
    l1 = 0
    r1 = s[clen] // i + 2
    while r1 - l1 > 1:
        c1 = (l1 + r1) // 2

        l2 = -1
        r2 = clen
        while r2 - l2 > 1:
            c2 = (r2 + l2) // 2
            if c[c2] < c1:
                l2 = c2
            else:
                r2 = c2

        if (r2 - rest) * c1 <= s[r2]:
            l1 = c1
        else:
            r1 = c1
    print(l1)

Submission status: Accepted

Solution code:
import bisect,copy

N=int(input())
A=list(map(int,input().split()))

data=[0 for i in range(0,N+1)]
for i in range(0,N):
    data[A[i]]+=1

X=[]
for i in range(0,N+1):
    if data[i]!=0:
        X.append(data[i])

X.sort()
n=len(X)
Y=copy.copy(X)
for i in range(1,n):
    Y[i]+=Y[i-1]

ans={i:0 for i in range(0,N+1)}
ans[0]=float('inf')
#num以下の整数の和+num*(num+1以上の個数)
for i in range(1,N+1):
    index=bisect.bisect_left(X,i+1)
    if index!=0:
        t=Y[index-1]+(n-index)*i
    else:
        t=(n-index)*i
    ans[i]=t//i


pointer=N
i=1
while N+1>i:
    if ans[pointer]>=i:
        print(pointer)
        i+=1
    else:
        pointer-=1

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import bisect
from collections import Counter

n = ni()
a = na()

c = sorted(Counter(a).values())
cc = [0]
m = len(c)
for i in c:
    cc.append(cc[-1]+i)

def is_ok(k,arg):
    b = bisect.bisect_right(c,arg)
    p = cc[b] + (m-b)*arg
    return True if p >= arg*k else False

for k in range(1,n+1):
    if k > m:
        print(0)
        continue
    #にぶたん
    ok,ng = -1,n//k+1
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(k,mid):
            ok = mid
        else:
            ng = mid
    
    print(ok)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import accumulate
import bisect
n = int(input())
a = list(map(int,input().split()))
c = list(Counter(a).items())
c = list(list(zip(*c))[1])
c.sort()
xls = [0]*(n+1)
for i in range(1,n+1):
  geqx = len(c)-bisect.bisect_left(c,i)
  xls[i] = xls[i-1]+geqx
xlsacc = list(accumulate(xls))
for k in range(1,n+1):
  l = 0
  r = n+1
  while l+1<r:
    x = (l+r)//2
    if k*x <= xls[x]:
      l = x
    else:
      r = x
  print(l)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
import collections
c=collections.Counter(l)
l=[0]+list(c.values())
c=collections.Counter(l)
l=list(c.items())
l.sort()
l.append((n,0))
acc=[0 for i in range(n+2)]
for i,j in l:
    acc[i]+=j
for i in range(1,n+1):
    acc[-i-1]+=acc[-i]
ans=[0 for i in range(n+1)]
t=0
for i,j in zip(l,l[1:]):
    a,b=i
    c,d=j
    t+=a*b
    for i in range(a+1,c+1):
        for j in range(acc[i+1],acc[i]+t//i+1):
            ans[j]=i
for i in ans[1:]:
    print(i)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
d = Counter(c.values())

dx = [0 for _ in range(n+1)]
for i in range(1, n+1):
	dx[i] = dx[i-1] + i*d[i]

xdx = [0 for _ in range(n+2)]
xdx[n] = d[n]
for i in range(n-1, 0, -1):
	xdx[i] = xdx[i+1] + d[i]

res = [0] + [(dx[i] + i*xdx[i+1]) // i for i in range(1, n+1)]
ans = [0 for _ in range(n)]
cur = n
for i in range(n):
	while cur > 0 and res[cur] < i+1:
		cur -= 1
	if cur > 0:
		ans[i] = cur
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
from itertools import accumulate

N, *A = map(int, open(0).read().split())

C = [0] * (N + 1)
D = [0] * (N + 1)
for a in A:
    C[a] += 1
    D[C[a]] += 1

T = [0] + [s // i for i, s in enumerate(accumulate(D[1:]), 1)]

ans = []
x = N
for k in range(1, N + 1):
    while 0 < x and T[x] < k:
        x -= 1
    ans.append(x)

print("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter

N = int(input())
A = list(map(int, input().split()))

C = sorted(list(Counter(A).values()), reverse=True)
L = len(C)
B = []

num = C[0]
for i, c in enumerate(C):
    for _ in range(num-c):
        B.append(i)
    num = c
for _ in range(num):
    B.append(L)

ans = [N]
for n in range(2, N+1):
    if n > L:
        ans.append(0)
        continue
    count = 0
    stack = []
    for b in B:
        tmp = b
        while stack:
            if tmp >= n:
                last = stack.pop()
                tmp = tmp + last - n
                count += 1
            else:
                break
        count += tmp//n
        stack.append(tmp%n)
    ans.append(count)

print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from bisect import bisect_left

N = int(input())
A = list(map(int, input().split()))

lst = [0] * (N)
for a in A:
    lst[a - 1] += 1
lst.sort() #頻度列

s = [0] * (N + 1)
for i in range(N):
    s[i + 1] = s[i] + lst[i]

# print (lst)
# print (s)

# def check(x, k):
#     i = bisect_left(lst, x) - 1
#     total = x * (N - i) + s[i]
#     return total >= x * k


ans = N
i = N
for k in range(1, N + 1):
    while True:
        while  i >= 1 and lst[i - 1] >= ans:
            i -= 1
        total = ans * (N - i) + s[i]
        if total >= ans * k:
            break
        ans -= 1
    # print ('i =', i)
    print (ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

N = int(input())
A = list(map(int, input().split()))

lst = [0] * (N + 1)
for a in A:
    lst[a - 1] += 1
lst.sort() #頻度列

s = [0] * (N + 1)
for i in range(N):
    s[i + 1] = s[i] + lst[i + 1]

# print (lst)
# print (s)

def check(x, k):
    i = bisect_left(lst, x) - 1
    total = x * (N - i) + s[i]
    return total >= x * k

ans = N
for k in range(1, N + 1):
    while True:
        if check(ans, k):
            break
        ans -= 1
    print (ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

N = int(input())
A = list(map(int, input().split()))

lst = [0] * (N + 1)
for a in A:
    lst[a - 1] += 1
lst.sort() #頻度列

s = [0] * (N + 1)
for i in range(N):
    s[i + 1] = s[i] + lst[i + 1]

# print (lst)
# print (s)

def check(x, k):
    i = bisect_left(lst, x) - 1
    total = x * (N - i) + s[i]
    return total >= x * k


for k in range(1, N + 1):
    l = 0 #OK
    r = N // k + 1 #NG
    while l + 1 < r:
        c = (l + r) // 2
        if check(c, k):
            l = c
        else:
            r = c
    print (l)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
from collections import Counter
from bisect import bisect
vs = list(Counter(A).values())
vs.sort()
cums = [0]
for v in vs:
    cums.append(cums[-1] + v)

def is_ok(k,m):
    j = bisect(vs,m)
    z = cums[j] + m*(len(vs)-j)
    return z >= m*k

ans = []
for k in range(1,N+1):
    if k > len(vs):
        ans.append(0)
    else:
        ok = 0
        ng = N//k + 1
        while ng-ok > 1:
            m = (ok+ng)//2
            if is_ok(k,m):
                ok = m
            else:
                ng = m
        ans.append(ok)

print(*ans, sep='\n')

Submission status: Accepted

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

rest = N
removed = 0
for K in range(1, N + 1):
    d = K - removed
    while C and C[- 1] > rest//d:
        rest -= C[- 1]
        C.pop()
        removed += 1
        d -= 1
    print(rest//d)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
"""
.2分探索を考える
.各kに対してx回以上抜き出せるかという問いを考える
.各数の個数を数えて数iの個数をCiとする
.各数iを抜き出せるのはCiまで
 ⇒各数を抜き出す回数min(Ci,x)
.Σmin(Ci,x)はkx以上でなければいけない(k個x回抜き出すため)
.これを満たすときx回抜き出せる
.このままではO(n^2(logn))なので工夫する
.Σ(min(Ci,x))はk依存でないのでここを工夫する(Σ(min(Ci,x))をSxとする)
.SxはSx-1と比べてx以上のCiの数だけ増える(x以上のCiの数をDxとする)
.Sx := Sx-1 + Dx
.Dxを求める時はCのリストについてbisectを行う。
⇒Ciの個数のリストdを用意してdの累積和を用意しておくとO(n)
.Sx >= k*xとなるxの最大値を2分探索で求める。(O(nlogn))
⇒変形すると,Sx/x >= kであり、各kに対してSx/xは単調減少なのでO(n)
"""
n = I()
a = LI()
cnt = list(Counter(a).values())
d = [0]*(n+1)
for i in cnt:
    d[i] += 1
d = list(accumulate(d))
m = d[-1]
S = [0]*(n+1)
for i in range(1,n+1):
    S[i] = S[i-1] + (m - d[i-1]) 
S2 = [0]*(n+1)
for i in range(1,n+1):
    S2[i] = S[i]//i
tmp = n
for k in range(1,n+1):
    while S2[tmp] < k:
        tmp -= 1
        if tmp <= 0:
            print(0)
            break
    else:
        print(tmp)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
"""
.2分探索を考える
.各kに対してx回以上抜き出せるかという問いを考える
.各数の個数を数えて数iの個数をCiとする
.各数iを抜き出せるのはCiまで
 ⇒各数を抜き出す回数min(Ci,x)
.Σmin(Ci,x)はkx以上でなければいけない(k個x回抜き出すため)
.これを満たすときx回抜き出せる
.このままではO(n^2(logn))なので工夫する
.Σ(min(Ci,x))はk依存でないのでここを工夫する(Σ(min(Ci,x))をSxとする)
.SxはSx-1と比べてx以上のCiの数だけ増える(x以上のCiの数をDxとする)
.Sx := Sx-1 + Dx
.Dxを求める時はCのリストについてbisectを行う。
.Sx >= k*xとなるxの最大値を2分探索で求める。(O(nlogn))
"""
n = I()
a = LI()
cnt = list(Counter(a).values())
cnt.sort()
m = len(cnt)
S = [0]*(n+1)
for x in range(1,n+1):
    l = bl(cnt,x)
    S[x] = S[x-1] + (m-l)
for k in range(1,n+1):
    high,low = n+1,0
    while high - low > 1:
        mid = (high + low)//2
        if S[mid] >= k*mid:
            low = mid
        else:
            high = mid
    print(low)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

def bisection(l,r,f,left=True,discrete=True):
    eps=1 if(discrete) else 10**-8
    if((not left)^f(r)): return r if(left) else r+1
    elif(left^f(l)): return l-1 if(left) else l
    while(r-l>eps):
        h=(l+r)//2 if(discrete) else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if(not discrete) else l if(left) else r

from collections import defaultdict
from bisect import bisect_left
def resolve():
    n=int(input())
    D=defaultdict(int)
    for a in map(int,input().split()):
        D[a]+=1

    D=list(D.values())
    D.sort()
    t=len(D)
    S=[0]*(t+1)
    for i in range(t):
        S[i+1]=S[i]+D[i]

    k=0
    def check(t):
        # t 以下のものの総和
        i=bisect_left(D,t)
        score=S[i]+t*(len(D)-i)
        return score>=k*t

    for k in range(1,n+1):
        print(bisection(0,n//k+1,check))
resolve()

Submission status: Accepted

Solution code:
from collections import Counter as C
N = int(input())
A = sorted(list(C([int(a) for a in input().split()]).values()))
X = [0] * 303030
for a in A:
    X[a] += 1

s = 0
c = 0
B = [0] * 303030
for i in range(300030)[::-1]:
    s += c
    B[i] += s
    c += X[i]

def chk(k, a):
    if N - B[a] >= k * a: return 1
    return 0

for i in range(1, N+1):
    l, r = 0, N + 1
    while r-l > 1:
        m = (l+r) // 2
        if chk(i, m):
            l = m
        else:
            r = m
    print(l)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import accumulate
N = int(input())
As = map(int, input().split())
xs = [0] + sorted([x for x in Counter(As).values()]) + [10**18]
Xs = accumulate(xs)
M = len(xs)-2
rs = [0]*N
mn = N+1
for l, (x, X) in enumerate(zip(xs[1:], Xs)):
    l = M-l
    k = X//(x+1)+l+1
    if x <= X//(k-l):
        k+=1
    for i in range(k, mn):
        rs[i-1] = X//(i-l)
    mn = min(k, mn)
for r in rs:
    print(r)

Submission status: Accepted

Solution code:
I = int(input())
from collections import Counter
from itertools import accumulate
As = map(int, input().split())
xs = sorted([x for x in Counter(As).values()]) + [10**18]
Xs = accumulate(xs)

N = len(xs) - 1
rs = [0]*I
mny = N+1
for l, (x, X) in enumerate(zip(xs[1:], Xs)):
    l += 2
    y = X//(x+1) + (N-l+1) + 1
    for i in range(y, mny):
        rs[i-1] = X//(i-(N-l+1))
    mny = min(y, mny)
for r in rs:
    print(r)

Submission status: Accepted

Solution code:
I = int(input())
from collections import Counter
from itertools import accumulate
As = map(int, input().split())
xs = sorted([x for x in Counter(As).values()]) + [10**18]
Xs = accumulate(xs)

N = len(xs) - 1
rs = [0]*I
mny = N+1
for l, (x, X) in enumerate(zip(xs[1:], Xs)):
    l += 2
    y = X//(x+1) + (N-l+1) + 1
    if y-(N-l+1) > 0 and x <= X//(y-(N-l+1)):
        y+=1
    for i in range(y, mny):
        rs[i-1] = X//(i-(N-l+1))
    mny = min(y, mny)
for r in rs:
    print(r)

Submission status: Accepted

Solution code:
I = int(input())
from collections import Counter
from itertools import accumulate
As = map(int, input().split())
xs = sorted([x for x in Counter(As).values()]) + [10**18]
Xs = accumulate(xs)

def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return min_i - 1
    index = (max_i + min_i)//2
    while True:
        if func(index) <= target:
            if target < func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1

#for x in xs:
N = len(xs) - 1
rs = [0]*I
mny = N+1
for l, (x, X) in enumerate(zip(xs[1:], Xs)):
    l += 2
    y = bsearch(0, N-l+2, N+1, lambda k: x > X//(k-(N-l+1)))
    y+=1
    #print(l, y, X//(y-(N-l+1)))
    for i in range(y, mny):
        rs[i-1] = X//(i-(N-l+1))
    mny = min(y, mny)
for r in rs:
    print(r)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
count = {}
for x in map(int, input().split()):
    count[x] = count.get(x, 0) + 1

a = sorted(count.values())
sums = a[:]
n = len(a)
for i in range(1, n):
    sums[i] += sums[i-1]
    
def check(k, x):
    pos = bisect.bisect_right(a, x)
    if pos == 0:
        return x * n >= k * x
    return sums[pos-1]+ x * (n - pos) >= k * x

x = N
for k in range(1, N + 1):
    while not check(k, x):
        x -= 1
    print(x)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
count = {}
for x in map(int, input().split()):
    count[x] = count.get(x, 0) + 1

a = sorted(count.values())
sums = a[:]
n = len(a)
for i in range(1, n):
    sums[i] += sums[i-1]
    
def check(k, x):
    pos = bisect.bisect_right(a, x)
    if pos == 0:
        return x * n >= k * x
    return sums[pos-1]+ x * (n - pos) >= k * x

x = 0
res = []
for k in range(N, 0, -1):
    while check(k, x+1):
        x += 1
    res.append(x)
    
for x in res[::-1]:
    print(x)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import bisect
from collections import Counter
def solve():
  n = int(input())
  a = sorted(list(int(i) for i in input().split()))
  c = Counter(a)
  val = list(c.values())
  val.sort()
  ans = [0]*(n+1)
  t = len(val)
  for i in range(1,n+1):
    place = bisect.bisect_left(val,i)
    ans[i] = ans[i-1]+t-place
  for i in range(1,n+1):
    ok = 0
    ng = n+1
    while ng-ok > 1:
      mid = (ok+ng)//2
      if ans[mid] >= i*mid:
        ok = mid
      else:
        ng = mid
    print(ok)
  
solve()

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
As = list(map(int, input().split()))

cntA = Counter(As)
cntCntA = Counter(cntA.values())

accDs = [cntCntA[0]]
for i in range(1, N+1):
    accDs.append(accDs[-1] + cntCntA[i])

accKDs = [0]
for i in range(1, N+1):
    accKDs.append(accKDs[-1] + i*cntCntA[i])

fXs = [0]
for X in range(1, N+1):
    fXs.append((accKDs[X] + X*(accDs[N]-accDs[X])) // X)

anss = [0] * (N+1)
for X, fX in enumerate(fXs):
    anss[fX] = X

for i in reversed(range(N)):
    if anss[i] == 0:
        anss[i] = anss[i+1]

print('\n'.join(map(str, anss[1:])))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



def bi_search(k):
    ok = 0
    ng = n // k + 1
    while ng > ok + 1:
        mid = (ng + ok) // 2
        if calc(mid, k):
            ok = mid
        else:
            ng = mid
    return ok


def calc(x, k):
    # x回できるか?
    l = bisect_left(L, (x, 0))
    # 全部使えるのが左側、l回しか使えないのが右側。
    if kv_acc[l - 1] + acc[l] * x >= k * x:
        return True
    else:
        return False




n = I()
A = LI()
L = [(0, 0)] + sorted([(k, v) for k, v in Counter(Counter(A).values()).items()])
m = len(L)
acc = [0] * (m + 1)
for i in range(m - 1, -1, -1):
    acc[i] = acc[i + 1] + L[i][1]

kv_acc = list(accumulate([k * v for k, v in L]))
for k in range(1, n + 1):
    print(bi_search(k))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
types = {}
for i in A: types[i] = types.get(i, 0) + 1
A = sorted([types[k] for k in types], reverse=True)
L = len(A)
cumsum = [0 for i in range(L+1)]
for i in range(L-1, -1, -1):
    cumsum[i] = A[i] + cumsum[i+1]



def getMidPoint(lo, hi, O):
    if lo >= hi: return lo
    mid = lo + (hi - lo+1) // 2
    if A[mid] > O:
        return getMidPoint(mid, hi, O)
    else:
        return getMidPoint(lo, mid-1, O)

getMid = [getMidPoint(0, L - 1, o) for o in range(N+1)]

# Highest K for given O
def calc(O):
    

    mid = getMid[O]
    if A[mid] < O: mid = - 1
    return (mid+1) + cumsum[mid+1] // O

for K in range(1, N+1):
    def getO(lo, hi):
        if lo >= hi: return lo
        mid = lo + (hi - lo+1) // 2
        if calc(mid) < K:
            return getO(lo, mid - 1)
        else:
            return getO(mid, hi)
        
    print(getO(0, N))

Submission status: Accepted

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

#input
N = int(input())
A = list(map(int, input().split()))

#output
from collections import Counter
import bisect

l = Counter(A).most_common()
l = [b for a, b in l]
M = len(l)
l.sort()
p = sum(l)

maximum_operation = [0] * N

ll = []
for x in reversed(range(1, N+1)):
    a = bisect.bisect_left(l, x)
    if a == 0:
        b = M*x
        c = 0
    elif a >= M:
        b = 0
        c = p
    else:
        b = (M-a)*x
        c = sum(l[0:a]) 
    ll.append((b + c)/x)

for K in range(M):
    maximum_operation[K] = N - bisect.bisect_left(ll, K+1)

for m in maximum_operation:
    print(m)

Submission status: Accepted

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

n = int(input())
a = [int(item) for item in input().split()]
cnt = [0] * (n + 1)
for item in a:
    cnt[item] += 1
cnt.sort()
cumsum = [0] * (n + 2)
for i in range(n+1):
    cumsum[i+1] = cumsum[i] + cnt[i]

indexes = [0] * (n+1)
for i in range(n+1):
    indexes[i] = bisect.bisect_left(cnt, i) - 1

ans = []
for i in range(n):
    if cnt[i+1] == 0:
        ans.append(0)
        continue
    l = 0; r = n+1
    while r - l > 1:
        mid = (l + r) // 2
        index = indexes[mid]
        if index <= i:
            l = mid
            continue
        num = index - i
        if mid * num <= cumsum[index + 1]:
            l = mid
        else:
            r = mid
    ans.append(l)

ans.reverse()
print("\n".join([str(item) for item in ans]))

Submission status: Accepted

Solution code:
n, *a = open(0).read().split()
n = int(n)
a = list(map(int, a))
sum = [0] * -~n
o = [0] * -~n
ct = [0] * -~n
b = []
for i in a:
    ct[i] += 1
for i in range(1, n + 1):
    if ct[i]:
        b.append(i)
b.sort(key=lambda x: ct[x])

for i in range(len(b)):
    sum[i] += (sum[i - 1] if i else 0) + ct[b[i]]

j = len(b) - 1
cnt = 0
for i in range(1, n + 1)[::-1]:
    while j >= 0 and ct[b[j]] >= i:
        cnt += 1
        j -= 1
    o[i] = (sum[j] if j >= 0 else 0) // i + cnt

ans = [0]
j = n
for i in range(1, n + 1):
    while j and o[j] < i:
        j -= 1
    ans.append(j)

print(*ans[1:])

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
c = Counter(map(int, input().split()))
cnt = sorted(c.values())

x = [0]*(n+1)
ad = [0]*(n+1)

for i in cnt:
    x[0] += 1
    x[i] -= 1
    ad[i] += i
    ad[-1] -= i

for i in range(n):
    x[i+1] += x[i]
    ad[i+1] += ad[i]

b = [0]*(n+1)
for i in range(n):
    b[i] = x[i] + ad[i]//(i+1)

prev = 0
ans = [0]*n
for i in reversed(range(n)):
    if prev !=b[i]:
        for j in range(prev, b[i]):
            ans[j] = i+1
        prev = b[i]
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
import collections
import numpy as np

# リストarrからx個の同じ長さの列を取り出す時の最大の長さ
# 発想: x個取り出す時、ある文字をx個より多く取り出して列に含むことはない
#       一方ある文字をその文字がある数よりも取り出して使うこともできない
#       つまり、min(arr.count(a), x)で、x個の同じ長さの列に使えるaの数がわかる
#       さらに、sum(min(arr.count(a),x))で、x個の同じ長さの列に使える文字の数がわかる
#       よって、sum(min(arr.count(a),x))//xで、x個の同じ長さの列の長さがわかる
#       発展的に、longest(arr,x)までの計算状況からlongest(arr,x+1)が計算できる
# def longest(arr, x):    # legacy
#     return sum(min(arr.count(a), x) for a in arr) // x


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

counter = collections.Counter(a)        #O(n)
nums = list(counter.values())           #O(n)
num_counter = collections.Counter(nums) #O(n)
lastest_add = np.count_nonzero(nums)    #O(n)
building, longests = [0], [0]
for i in range(1, n+1):                 #O(n)
    appended = building[-1] + lastest_add   #O(1)
    building.append(appended)               #O(1)
    longests.append(appended // i)          #O(1)
    lastest_add -= num_counter[i]           #O(1)


lastest_longest = 0
k_most = []
for i, x in enumerate(reversed(longests)):
    while x > lastest_longest:
        lastest_longest += 1
        k_most.append(n-i)

k_most.extend([0]*(n-len(k_most)))      # zero padding

for longests_num in k_most:
    print(longests_num)

# print('----------------')
# for k in range(1, n+1):
#     maxindexes = list(i for i, x in enumerate(longests) if x >= k)
#     if maxindexes:
#         print(maxindexes[-1])
#     else:
#         print(0)

Submission status: Accepted

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

rest = N
removed = 0
for K in range(1, N + 1):
    d = K - removed
    while C and C[- 1] > rest//d:
        rest -= C[- 1]
        C.pop()
        removed += 1
        d -= 1
    print(rest//d)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter
from itertools import accumulate

N = int(input())
A = list(map(int,input().split()))

B = list(Counter(A).values())

C = [0] * N 
for i in B:
    C[i-1] += 1

F = list(accumulate(C))

S = [0] * N
f = [0] * N
S[0] = f[0] = sum(C) 
for i in range(2, N+1):
    S[i-1] = (S[i-2] + C[i-1] + S[0] - F[i-1] ) 
    f[i-1] = S[i-1] / i

f.sort()
n = 0     
K = 1
    
while K != N+1:
    if K <= f[n]:
        print(N-n)
        K += 1
    else:
        n += 1
    if n == N:
        for i in range(N-K+1):
            print(0)
        K = N+1

Submission status: Accepted

Solution code:
N = int(input())
A = map(int, input().split())
C = [0]*N
for a in A:
    C[a - 1] += 1
D = [0]*(N + 1)
for c in C:
    D[c] += 1

Dk_accum = [0]*(N + 1)
for i in range(1, N + 1):
    Dk_accum[i] = Dk_accum[i - 1] + i*D[i]
    
D_sum = sum(D)
D_accum = [0]*(N + 2)
D_accum[0] = D_sum
for i in range(1, N + 1):
    D_accum[i] = D_accum[i - 1] - D[i - 1]
    
F = [0]*(N + 1)
for i in range(1, N + 1):
    F[i] = (Dk_accum[i]//i + D_accum[i + 1])

i = N
for K in range(1, N + 1):
    while i > 0 and K > F[i]:
        i -= 1
    print(i)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter
from itertools import accumulate
from collections import defaultdict
INF = float("inf")


def solve(N: int, A: "List[int]"):
    c = Counter(A)
    d = Counter(c.values())
    d = tuple(accumulate([d[i] for i in range(N, -1, -1)]))[::-1]
    S = [0]*(N+1)
    for i in range(1, N+1):
        S[i] = S[i-1] + d[i]

    def isOK(y):
        return S[y] < K*y

    def binary_search(x):
        ng = -1
        ok = len(x)+1

        while abs(ok - ng) > 1:
            mid = (ok + ng)//2
            if isOK(mid):
                ok = mid
            else:
                ng = mid
        return ng, ok

    for K in range(1, N+1):
        ng, ok = binary_search(range(N))
        print(ng)

    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: Accepted

Solution code:
# coding: utf-8
# Your code here!
def f(m,k):#最初のm個, kずつ
    if m == 0: return 0
    if m < k: return 0
#    if (m,k) in memo:
#        return memo[(m,k)]
    z = 0
    if acc[m]//k >= c[m]:
        return acc[m]//k
    else:
        return f(m-1,k-1)


import sys
#sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

from itertools import accumulate

n = int(input())
a = [int(i) for i in readline().split()]

res = [0]*(n+1)
for i in a: res[i] += 1

c = [0]
for i in res:
    if i > 0: c.append(i)
c.sort()#reverse=True)

l = len(c)-1
#print(c)
acc = list(accumulate(c))

#print(acc,c)
res = [n]+[acc[m]//c[m] for m in range(1,l+1)]


#print(l,res)


m = l
for k in range(1,n+1):
    k -= l-m
    if res[m] >= k:
        print(acc[m]//k)
    else:
#        print(k,m)
        while res[m] < k:
            m -= 1
            k -= 1
        print(acc[m]//(k))