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:
#!/usr/bin/pypy
N=int(raw_input())
AN=map(int, raw_input().split())

BN=[0 for i in xrange(N)]
for i in AN:
    BN[i-1] += 1
BN.sort()

LN = [0 for i in xrange(N)]
s = 0
j = 0
try:
    for X in xrange(1, N+1):
        while j<N and  BN[j] < X:
            s += BN[j]
            j += 1
        LN[X-1] = int((s + X*(N - j)) / X)
except IndexError:
    pass

KN = [0 for i in xrange(N)]
for i in xrange(len(LN)):
    KN[LN[i]-1] = i+1

for i in xrange(len(KN)-2, -1, -1):
    if KN[i] == 0:
        KN[i] = KN[i+1]

for i in KN:
    print (str(i))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    c = sorted(collections.Counter(LI()).values(), reverse=True) + [0]
    ci = 0
    t = n
    r = [0]
    for i in range(n,0,-1):
        while c[ci] > i:
            ci += 1
        t -= ci
        r.append(t // i)

    rr = []
    r.reverse()
    ri = 0
    for i in range(n,0,-1):
        while r[ri] >= i:
            ri += 1
        rr.append(ri)

    rr.reverse()

    return JA(rr,"\n")


print(main())

Submission status: Accepted

Solution code:
# F - Distinct Numbers
from bisect import bisect_left

def isOK(c, k, N, L, cum_sum):
    i = bisect_left(L, c)
    s = c * (N - i) + cum_sum[i];
    return (s >= c * k)

N = int(input())
D = list(map(int, input().split()))
freq = [0] * N
for d in D:
    freq[d - 1] += 1
    
freq.sort()
cum_sum = [0] * (N + 1)
for i in range(N):
    cum_sum[i + 1] = cum_sum[i] + freq[i]
    
for k in range(1, N + 1):
    l = 0
    r = int(N / k) + 1
    while l + 1 < r:
        c = int((l + r) / 2)
        ok = isOK(c, k, N, freq, cum_sum)
        if ok:
            l = c
        else:
            r = c
    print(l)

Submission status: Accepted

Solution code:
N=int(raw_input())
AN=map(int, raw_input().split())

BN=[0 for i in xrange(N)]
for i in AN:
    BN[i-1] += 1
BN.sort()

LN = [0 for i in xrange(N)]
s = 0
j = 0
try:
    for X in xrange(1, N+1):
        while j<N and  BN[j] < X:
            s += BN[j]
            j += 1
        LN[X-1] = (s + X*(N - j)) / X
except IndexError:
    pass

KN = [0 for i in xrange(N)]
for i in xrange(len(LN)):
    KN[LN[i]-1] = i+1

for i in xrange(len(KN)-2, -1, -1):
    if KN[i] == 0:
        KN[i] = KN[i+1]

for i in KN:
    print (str(i))

Submission status: Accepted

Solution code:
import sys 
import collections as cl


N=int(input())
A=list(map(int,sys.stdin.readline().split()))
c=cl.Counter(A)
NumberTupleList=c.most_common()
NumberList=[x[1] for x in NumberTupleList[::-1]]
LengthOfNumberList=len(NumberList)
FormulaList=[0 for i in range(N)]
flag=0
S=sum(NumberList)
for x in range(1,N+1):
    while flag<LengthOfNumberList and NumberList[flag]<=x:
        flag+=1
    if flag<LengthOfNumberList:
        FormulaList[x-1]=(sum(NumberList[:flag])+x*(LengthOfNumberList-flag))/x
    else:
        FormulaList[x-1]=S/x
pin=N-1
for K in range(1,N+1):
    while pin>=0 and K>FormulaList[pin]:
        pin-=1
    print(pin+1)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect
N = int(input())
A = list(map(int,input().split()))

d = defaultdict(lambda:0)

for i in range(N):
    d[A[i]] += 1

C = [0]*(N+1)

for i in d:
    C[d[i]] += 1

C1 = [0]*(N+1)
C2 = [0]*(N+1)

for i in range(N):
    C1[i+1] = C1[i] + (i+1)*C[i+1]
    C2[i+1] = C2[i] + C[i+1]

l = [0]*N
for n in range(N):
    l[n] = C1[n+1]//(n+1)+C2[N]-C2[n+1]
    l[n] *= -1


for i in range(N):
    print(bisect(l,-(i+1)))

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_right
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
class CountUp:
    def __init__(self, start=0):
        self.index = start-1

    def __call__(self):
        self.index += 1
        return self.index

N = int(input())
A = inpl()
ui = defaultdict(CountUp())
B = []
Ns = 0
for a in A:
    i = ui[a]
    if i >= Ns:
        Ns += 1
        B.append(1)
    else:
        B[i] += 1
B.sort()
C = []
prev = B[0]
n = 0
for b in B:
    if b == prev:
        n += 1
    else:
        C.append((prev,n))
        prev = b
        n = 1
else:
    C.append((prev,n))

f = []
S = 0
T = Ns
nc = 0
nxtc = C[0][0]
for i in range(1,N+1):
    if i == nxtc:
        n = C[nc][1]
        S += i*n
        T -= n
        nc += 1
        if nc < len(C):
            nxtc = C[nc][0]
        else:
            nxtc = None
    f.append(-(S//i + T))

#print(f)

for K in range(1,N+1):
    print(bisect_right(f,-K))

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
B = [0]*(n+1)
C = [0]*(n+1)
for a in A:
    B[a] += 1
    C[B[a]] += 1

X = [0]
for i in range(1,n+1):
    X.append(X[i-1] + C[i])
for j in range(1,n+1):
    X[j] = X[j] // j

ind = n
k = 1
while k<=n:
    if ind<0:
        for _ in range(n-k+1):
            print(0)
        break
    if k<=X[ind]:
        print(ind)
        k += 1
    else:
        ind -= 1

Submission status: Accepted

Solution code:
import bisect

n = int(input())
A = list(map(int, input().split()))
counts = [0]*(n)
for a in A:
    counts[a-1] += 1
counts.sort()

cumsum = []
num = 0
for count in counts:
    num += count
    cumsum.append(num)

answers = [0]*(n)
for i in range(1, n+1):
    idx = bisect.bisect_right(counts, i)
    left = cumsum[idx-1]
    right = (n-idx)*i
    K = (right+left)//i
    answers[K-1] = i

now = 0
for i in range(n-1, -1, -1):
    if answers[i] == 0:
        answers[i] = now
    now = answers[i]

for ans in answers:
    print(ans)

Submission status: Accepted

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

A.sort()
D = [1]
t = A[0]
for i in range(1, N):
  if A[i] == t:
    D[-1] += 1
  else:
    D.append(1)
    t = A[i]

D.sort()
L = len(D)
S = [0] * L
S[0] = D[0]
for i in range(1, L):
  S[i] = S[i - 1] + D[i]

def hersCode(n):
  ok = 0
  ng = N + 1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if nasu(mid, n):
      ok = mid
    else:
      ng = mid
  return ok

def honya(n):
  ok = -1
  ng = L
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if D[mid] >= n:
      ok = mid
    else:
      ng = mid
  return ok + 1

def nasu(x, n):
  a = honya(x)
  ans = a * x + S[L - a - 1]
  if ans >= n * x:
    return True
  else:
    return False

D.sort(reverse = True)
for i in range(1, N + 1):
  if L < i:
    print(0)
    continue
  print(hersCode(i))

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = [int(i) for i in input().split()]

C = [0] * (N + 1)
S = [0] * (N + 1)

for a in Counter(A).values() :
    C[a] += 1
    S[a] += a

for i in range(1, N + 1) :
    C[i] += C[i-1]
    S[i] += S[i-1]

for K in range(1, N + 1) :
    ok, ng = 0, N + 1
    while ng - ok > 1 :
        mid = (ng + ok) // 2
        if S[mid] + mid * (C[-1] - C[mid]) >= K * mid :
            ok = mid
        else :
            ng = mid
    print(ok)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from collections import Counter
    n=int(input())
    A=list(Counter(map(int,input().split())).values())
    A.sort()
    m=len(A)
    S=[0]*(m+1) # cumulative distribution
    for i in range(m): S[i+1]=S[i]+A[i]
    # output
    from bisect import bisect_left
    p=n
    i=bisect_left(A,p) # pに応じてiが定まる
    for k in range(1,n+1):
        while(S[i]+p*(m-i)<k*p): # p>=0 and は書かなくてもよい
            p-=1
            i=bisect_left(A,p)
        print(p)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def bin_sort(A,n_min=None,n_max=None):
    if(n_min is None): n_min=min(A)
    if(n_max is None): n_max=max(A)
    bin=[0]*(n_max-n_min+1)
    for a in A: bin[a-n_min]+=1
    B=[]
    for i in range(n_min,n_max+1): B[len(B):len(B)]=[i]*bin[i-n_min]
    return B

def resolve():
    n=int(input())
    A=[0]*n
    for a in map(int,input().split()): A[a-1]+=1
    A=bin_sort(A,0,n)
    S=[0]*(n+1)
    for i in range(n): S[i+1]=S[i]+A[i]
    # output
    p=n; i=n
    for k in range(1,n+1):
        while(1):
            while(1):
                if(i<=0 or A[i-1]<p): break
                i-=1
            if(S[i]+p*(n-i)>=k*p): break
            p-=1
        print(p)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def bin_sort(A,n_min=None,n_max=None):
    if(n_min is None): n_min=min(A)
    if(n_max is None): n_max=max(A)
    bin=[0]*(n_max-n_min+1)
    for a in A: bin[a-n_min]+=1
    B=[]
    for i in range(n_min,n_max+1): B.extend([i]*bin[i-n_min])
    return B

def resolve():
    n=int(input())
    A=[0]*n
    for a in map(int,input().split()): A[a-1]+=1
    A=bin_sort(A,0,n)
    S=[0]*(n+1)
    for i in range(n): S[i+1]=S[i]+A[i]
    # output
    p=n; i=n
    for k in range(1,n+1):
        while(1):
            while(1):
                if(i<=0 or A[i-1]<p): break
                i-=1
            if(S[i]+p*(n-i)>=k*p): break
            p-=1
        print(p)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def bin_sort(A,n_min=None,n_max=None):
    if(n_min is None): n_min=min(A)
    if(n_max is None): n_max=max(A)
    bin=[0]*(n_max-n_min+1)
    for a in A: bin[a-n_min]+=1
    B=[]
    for i in range(n_min,n_max+1):
        for _ in range(bin[i-n_min]): B.append(i)
    return B

def resolve():
    n=int(input())
    A=[0]*n
    for a in map(int,input().split()): A[a-1]+=1
    A=bin_sort(A,0,n)
    S=[0]*(n+1)
    for i in range(n): S[i+1]=S[i]+A[i]
    # output
    p=n; i=n
    for k in range(1,n+1):
        while(1):
            while(1):
                if(i<=0 or A[i-1]<p): break
                i-=1
            if(S[i]+p*(n-i)>=k*p): break
            p-=1
        print(p)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def bin_sort(A,n_min=None,n_max=None):
    if(n_min is None): n_min=min(A)
    if(n_max is None): n_max=max(A)
    bin=[0]*(n_max-n_min+1)
    for a in A: bin[a-n_min]+=1
    B=[]
    for i in range(n_min,n_max+1): B+=[i]*bin[i-n_min]
    return B

def resolve():
    n=int(input())
    A=[0]*n
    for a in map(int,input().split()): A[a-1]+=1
    A=bin_sort(A,0,n)
    S=[0]*(n+1)
    for i in range(n): S[i+1]=S[i]+A[i]
    # output
    p=n; i=n
    for k in range(1,n+1):
        while(1):
            while(1):
                if(i<=0 or A[i-1]<p): break
                i-=1
            if(S[i]+p*(n-i)>=k*p): break
            p-=1
        print(p)
resolve()

Submission status: Accepted

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

c = [0] * (N + 1)
Dx = [0] * (N + 1)
for a in A:
    c[a] += 1 #cは、aという数が出た回数を記録
    Dx[c[a]]+=1
    #Dxは、その回数のところに種類を記録。賢い。

Sx=[0]#初項は0
for j in range(1,N+1):
    Sx.append(Sx[j-1]+Dx[j])
#解法2を真似してみる。
for h in range(1,N+1):
    Sx[h]=Sx[h]/h

x=N
k=1
while k<N+1:
    if x<0:
        for _ in range(N-k+1):
            print(0)
        exit(0)
    if k<=Sx[x]:
        print(x)
        k+=1
    else:
        x-=1

Submission status: Accepted

Solution code:
n = int(input())
arr = list(map(int,input().split()))

from collections import Counter
c = Counter(arr)
c = list(c.values())
c.sort()
s = n

sol = []
removed = 0
for k in range(1,n+1):
    rest = k - removed
    while c and c[-1] > s//rest:
        s -= c[-1]
        c.pop()
        rest -= 1
        removed += 1
    sol.append(s//rest)

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

Submission status: Accepted

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

N = int(input())
a = list(map(int, input().split()))
c = sorted(list(Counter(a).values()))
M = len(c)
cs = [0]*(M+1)
for i in range(M):
    cs[i+1] = cs[i] + c[i]

kmax = [0] * (N+1)
for i in range(1, N+1):
    j = bisect.bisect_left(c, i) if i <= c[-1] else M
    kmax[i] = (cs[j] + i * (M-j)) // i

idx = N
for k in range(1, N+1):
    while k > kmax[idx]:
        if idx == 0:
            break
        idx -= 1
    print(idx)

Submission status: Accepted

Solution code:
import bisect
N=int(input())
A=list(map(int,input().split()))

D={}
for i in range(N):
    if A[i] not in D:
        D[A[i]]=1
    else:
        D[A[i]]+=1
        
D[0]=0
#print(D)
D=list(D.values())

D.sort()
#print(D)
B=[D[0]]
for i in range(1,len(D)):
    B.append(B[-1]+D[i])
D=D+[10**15]

#print(D)
#print(B)
cnt=N
for i in range(1,N+1):
    for j in range(N+1):
        C=bisect.bisect_left(D,cnt+0.1)
        if i*cnt<=B[C-1]+cnt*(len(B)-1-C+1):
            print(cnt)
            break
        else:
            cnt-=1

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from collections import Counter
    n=int(input())
    A=list(Counter(map(int,input().split())).values())
    A.sort()
    m=len(A)
    S=[0]*(m+1) # cumulative distribution
    for i in range(m): S[i+1]=S[i]+A[i]
    # output
    p=n
    i=m
    from bisect import bisect_left
    for k in range(1,n+1):
        while(1):
            # pに対して先にi_pを求めておく
            while(1):
                if(i<=0 or A[i-1]<p): break
                i-=1
            if(S[i]+p*(m-i)>=k*p): break # p<0 or を書く必要はない
            p-=1 # pの条件が真になるまで減らし続ける
        print(p)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from collections import Counter
    n=int(input())
    A=list(Counter(map(int,input().split())).values())
    A.sort()
    m=len(A)
    S=[0]*(m+1) # cumulative distribution
    for i in range(m): S[i+1]=S[i]+A[i]
    # output
    p=n
    i=m-1
    from bisect import bisect_left
    for k in range(1,n+1):
        while(1):
            # pに対して先にi_pを求めておく
            i=bisect_left(A,p)
            if(S[i]+p*(m-i)>=k*p): break
            p-=1 # pの条件が真になるまで減らし続ける
        print(p)
resolve()

Submission status: Accepted

Solution code:
import bisect as b
n = int(input())

d = [0]*n
for el in map(int, input().split()):
    d[el-1] += 1

d.sort()

s = [0]*(n+1)
for i in range(n):
    s[i+1] = s[i] + d[i]

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

Submission status: Accepted

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

from collections import Counter
from itertools import accumulate
from math import floor
from bisect import bisect_left


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

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

    d = Counter(c)
    d_li = [0] * (n + 1)
    for k, v in d.items():
        d_li[k] = v

    dk_acm = list(accumulate(d_li))

    kdk_acm = [0]
    for k, e in enumerate(d_li[1:], 1):
        kdk_acm.append(kdk_acm[-1] + k * e)

    def f(x):
        kdk_sm = kdk_acm[x]
        dk_sm = dk_acm[n] - dk_acm[x]

        return floor((kdk_sm + x * dk_sm) / x)

    fs = [float("inf")] + [f(x) for x in range(1, n + 1)]
    fs = fs[::-1]

    for k in range(1, n + 1):
        print(n - bisect_left(fs, k))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
a=[int(j) for j in input().split()]
from collections import Counter
c=Counter(a)
l=c.most_common()
ll=[]
for i,j in l:
    ll.append(j)
ll.sort()
s=sum(ll)
rem=0
for k in range(1,n+1):
    rest=k-rem
    while ll and ll[-1]>s//rest:
        s-=ll[-1]
        ll.pop()
        rem+=1
        rest-=1
    print(s//rest)

Submission status: Accepted

Solution code:
from collections import *
MAX = 3*pow(10,5) + 2
n = int(input())
a = list(map(int,input().split()))
b = [0 for i in range(MAX)]
c = [0 for i in range(MAX)]
for i in a:
    b[i] += 1
for i in b:
    c[i] += 1
s = n
last = n
print(last)
for k in range(2,n+1):
    while(s//k < last):
        best = min(last,s//k)
        for i in range(last,best,-1):
            s -= c[i]
            c[i-1] += c[i]
            c[i] = 0
        last = best
    print(last)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
a = list(map(int,input().split()))
a.sort()

#b:個数
b = []
cnt = 1
for i in range(1,n):
    if a[i] == a[i-1]:
        cnt += 1
    else:
        b.append(cnt)
        cnt = 1
b.append(cnt)
b.sort()

#p[i]:各々からi個以下取った時の最大個数
p = [0]*(n+1)
for i in range(1,n+1):
    kp = bisect.bisect_left(b,i)
    p[i] = p[i-1]+len(b)-kp


for k in range(1,n+1):
    ok = 0
    ng = n+1
    while abs(ng-ok) > 1:
        mid = (ok+ng)//2
        if p[mid] >= k*mid:
            ok = mid
        else:
            ng = mid
    print(ok)

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,discrete=True,left=True):
    eps=1 if discrete else 10**-12
    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 h if not discrete else l if left else r

def resolve():
    from collections import Counter
    from bisect import bisect_left
    n=int(input())
    A=Counter(map(int,input().split()))
    A=list(A.values())
    A.sort()
    m=len(A)
    S=[0]*(m+1)# cumulative distribution
    for i in range(m):
        S[i+1]=S[i]+A[i]
    for k in range(1,n+1):
        def check(p):
            i=bisect_left(A,p)
            return S[i]+(m-i)*p>=k*p
        print(bisection(0,n//k+1,check))
resolve()

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import groupby, accumulate

n = int(input())
aaa = list(map(int, input().split()))
cnt = sorted(Counter(aaa).values())

remain = len(cnt)
total = 0
kkk = [0] * (n + 1)
p = 1

for c, itr in groupby(cnt):
    l = len(list(itr))
    for i in range(p, c + 1):
        kkk[remain + total // i] = i
    remain -= l
    total += c * l
    p = c + 1

for i in range(p, n + 1):
    kkk[remain + total // i] = i

kkk.reverse()
kkk = list(accumulate(kkk, func=max))
kkk.reverse()

print(*kkk[1:])

Submission status: Accepted

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

# Cのうちx以上のものの個数D[x]を計算(x=0,...,N)
D=[L-bisect.bisect_left(C,x) for x in range(N+1)]
S=[0]
for n in range(1,N+1):
    S.append(S[-1]+D[n])

# T[x]=S[x]/x(x=1,...,N)としてKをbisect_rightで挿入した時のindexが答え
T=[x/S[x] for x in range(1,N+1)]
for K in range(1,N+1):
    print(bisect.bisect_right(T,1/K))

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import groupby


def bin_search(k, greater_count, smaller_sum):
    l = 0
    r = n + 1
    while l < r - 1:
        m = (l + r) // 2
        gc = greater_count[m]
        ss = smaller_sum[m]
        if gc + ss // m >= k:
            l = m
        else:
            r = m
    return l


n = int(input())
aaa = list(map(int, input().split()))
cnt = sorted(Counter(aaa).values())

# Precompute
greater_count = [0] * (n + 2)  # Number of types of Ai same or greater than i
smaller_sum = [n] * (n + 2)  # Number of Ai smaller than i

remain = greater_count[1] = len(cnt)
total = smaller_sum[1] = 0

cnt_grp = [(c, len(list(itr))) for c, itr in groupby(cnt)]

for (c, l), (c2, _) in zip(cnt_grp, cnt_grp[1:]):
    remain -= l
    total += c * l
    for i in range(c + 1, c2 + 1):
        greater_count[i] = remain
        smaller_sum[i] = total

# print(greater_count)
# print(smaller_sum)

# Query
buf = []
for k in range(1, len(cnt) + 1):
    buf.append(bin_search(k, greater_count, smaller_sum))

buf.extend([0] * (n - len(cnt)))

print(*buf)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import groupby


def bin_search(k, greater_count, smaller_sum):
    l = 0
    r = n + 1
    while l < r - 1:
        m = (l + r) // 2
        gc = greater_count[m]
        ss = smaller_sum[m]
        if gc + ss // m >= k:
            l = m
        else:
            r = m
    return l


n = int(input())
aaa = list(map(int, input().split()))
cnt = sorted(Counter(aaa).values())

# Precompute
greater_count = [0] * (n + 2)  # Number of types of Ai same or greater than i
smaller_sum = [n] * (n + 2)  # Number of Ai smaller than i

remain = greater_count[1] = len(cnt)
total = smaller_sum[1] = 0
pointer = 2

for c, itr in groupby(cnt):
    l = len(list(itr))
    remain -= l
    total += c * l
    for i in range(pointer, c + 2):
        greater_count[i] = remain
        smaller_sum[i] = total
    pointer = c + 2

# print(greater_count)
# print(smaller_sum)

# Query
buf = []
for k in range(1, len(cnt) + 1):
    buf.append(bin_search(k, greater_count, smaller_sum))

buf.extend([0] * (n - len(cnt)))

print(*buf)

Submission status: Accepted

Solution code:
import itertools
import collections
N = int(input())
A = [int(_) for _ in input().split()]
c = sorted(collections.Counter(A).values())
acc = list(itertools.accumulate([0] + c))
n = len(acc) - 1
j = 0
for i in range(1, n + 1):
    r = 0
    while i - j > 0:
        if (i - j) * c[-1 - j] <= acc[-1 - j]:
            r = acc[-1 - j] // (i - j)
            break
        else:
            j += 1
    print(r)
for _ in range(N - n):
    print(0)

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# 解説AC
# https://img.atcoder.jp/abc143/editorial.pdf
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

A = np.array(A, dtype=int)
C = np.bincount(A, minlength=N + 2)
D = np.bincount(C, minlength=N + 2)

ld = (D * np.arange(len(D))).cumsum()
ud = D[::-1].cumsum()[::-1]

X = np.arange(1, N + 1, dtype=int)
# L[x]: x 回取れるときの最大の長さ k
L = np.zeros(N + 1, dtype=int)
L[X] = (ld[X] + X * ud[X + 1]) // X

i = len(L) - 1
for k in range(1, N + 1):
    while i > 0 and L[i] < k:
        i -= 1
    print(i)

Submission status: Accepted

Solution code:
import collections
import bisect
n=int(input())
a=collections.Counter(map(int,input().split()))
a=list(a.values())
a.sort()
b=[0]*len(a)
b[0]=a[0]
for i in range(len(a)-1):
    b[i+1]=b[i]+a[i+1]
s=sum(a)
ans=[i for i in range(0,n+1)]
ans=ans[::-1]
for t in range(1,n+1):
    ANS=ans[n+(-n//t):]
    for A in ANS:
        z=bisect.bisect_right(a,A)
        if A*t<=(b[z-1] if z>=1 else 0)+A*(len(b)-z):
            print(A)
            break

Submission status: Accepted

Solution code:
import collections
import bisect
n=int(input())
a=collections.Counter(map(int,input().split()))
a=list(a.values())
a.sort()
b=[0]*len(a)
b[0]=a[0]
for i in range(len(a)-1):
    b[i+1]=b[i]+a[i+1]
s=sum(a)
#print(a,b)
ans=[i for i in range(0,n+1)]
ans=ans[::-1]
for t in range(1,n+1):
    ANS=ans[n+(-n//t):]
    #print(ANS)
    for A in ANS:
        z=bisect.bisect_right(a,A)
        #print(z)
        if A*t<=(b[z-1] if z>=1 else 0)+A*(len(b)-z):
            print(A)
            break

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  input()
  cards = list(map(int, input().split()))
  counts = [0] * len(cards)
  values = [0] * len(cards)

  for c in cards:
    c -= 1
    values[counts[c]] += 1
    counts[c] += 1

  lengths = []
  used = 0

  for i, v in enumerate(values):
    used += v
    lengths.append(used // (i + 1))

  number = len(lengths) - 1

  for k in range(1, len(cards) + 1):
    while number >= 0 and lengths[number] < k:
      number -= 1
    print(number + 1)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# 解説AC
# https://twitter.com/maspy_stars/status/1185552225474498560
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

C = list(np.bincount(A).tolist())
C.sort()
deleted = 0
S = N


def solve(k):
    global S, deleted

    k -= deleted
    while k > 0 and C[-1] > S // k:
        S -= C.pop()
        deleted += 1
        k -= 1
    if k > 0:
        return S // k
    return 0


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

Submission status: Accepted

Solution code:
import os
import sys

# import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# 解説AC
# https://twitter.com/maspy_stars/status/1185552225474498560
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def test(k):
    bc = np.bincount(A)
    bc.sort()
    bc = bc[np.searchsorted(bc, 1):]
    bc = bc[::-1]
    ret = 0

    while len(bc) >= k:
        bc[:k] -= 1
        bc.sort()
        bc = bc[np.searchsorted(bc, 1):]
        bc = bc[::-1]
        ret += 1
    return ret


def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    :return:
    """
    s = 0
    ret = []
    for a in it:
        s += a
        ret.append(s)
    return ret


C = [0] * (N + 1)
for a in A:
    C[a] += 1
C.sort()
cs = list(reversed(cumsum(reversed(C))))


def solve(k):
    cnt = N // k
    if C[-1] <= cnt:
        # 全部取れるとしていい
        # 最後に2つ以上余ると max_c <= cnt に矛盾する
        return cnt

    # S = N
    # i = 1
    # while i < k:
    #     # 最大値は毎回取ることにしてもう見ない
    #     S -= C[-i]
    #     cnt = S // (k - i)
    #     max_c = C[-i - 1]
    #     if max_c <= cnt:
    #         return cnt
    #     i += 1

    ng = 0
    ok = k
    while abs(ng - ok) > 1:
        i = (ng + ok) // 2
        s = N - cs[-i]
        cnt = s // (k - i)
        max_c = C[-i - 1]
        if max_c <= cnt:
            ok = i
        else:
            ng = i
    if ok < k:
        i = ok
        s = N - cs[-i]
        return s // (k - i)
    else:
        return 0


ans = [0] * N
for k in reversed(range(1, N + 1)):
    ans[k - 1] = solve(k)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
def f_distinct_numbers():
    # 参考: http://drken1215.hatenablog.com/entry/2019/10/20/003400
    from collections import Counter
    N = int(input())
    A = [int(i) for i in input().split()]

    c = [0] * (N + 1)  # c[k]: A の中に k が何回現れたか
    d = [0] * (N + 1)  # d[x]: c の中に x 以上の要素が何個あるか (0番は使わない)
    for a in A:
        c[a] += 1
        d[c[a]] += 1

    cumsum = [0] * (N + 1)  # リスト d の累積和
    judge = [0] * (N + 1)
    for i in range(1, N + 1):
        cumsum[i] = cumsum[i - 1] + d[i]
        judge[i] = cumsum[i] // i

    # 各 k ごとに k <= cumsum[x] // x (judge[x]) を満たす最大の x を求める
    ans = []
    x = N
    for k in range(1, N + 1):
        while x > 0 and k > judge[x]:  # 条件を満たさなくなるまで x を減らす
            x -= 1
        ans.append(x)
    return ' '.join(map(str, ans))

print(f_distinct_numbers())

Submission status: Accepted

Solution code:
import sys
from collections import Counter

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()
    cs = [0]
    s = 0
    for a in aa:
        s += a
        cs += [s]
    # print(aa)
    # print(cs)
    ans = n + 1
    i = len(aa)
    for k in range(1, n + 1):
        while 1:
            while i > 0 and aa[i - 1] >= ans:
                i -= 1
            s = cs[i] + ans * (len(aa) - i)
            if s >= ans * k:
                break
            else:
                ans -= 1
        print(ans)

main()

Submission status: Accepted

Solution code:
N = int(input())
 
A = list(map(int,input().split()))
 
dic = {}
 
for a in A:
 
    if a not in dic:
        dic[a] = 1
    else:
        dic[a] += 1
 
B = []
for i in dic:
    B.append(dic[i])
 
B.sort()
 
B_sub = B.copy()
 
for i in range(len(B)-1):
    B_sub[i+1] += B_sub[i] 
 
aind = N + 1
nind = len(B) - 1
 
#print (B,B_sub)
 
for i in range(N):
 
    i += 1
 
    while True:
 
        while nind > 0 and B[nind] > aind - 1:
 
          nind -= 1
 
        if i > len(B):
            print (0)
            break
 
        elif ((len(B) - 1) - nind ) * (aind-1) + B_sub[nind] >= (aind - 1) * i:
            print (aind - 1)
            break
 
        aind -= 1