Problem p02890 (python)

Fixed submission:
#!/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)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
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()))


n = I()
a = LI()
c = list(Counter(a).items())
x = len(c)
H = []
for i,j in c:
    heappush(H,j)
for k in range(1,n+1):
    if k == 1:
        print(n)
        continue
    h = H.copy()
    x = len(h)
    if k > x:
        print(0)
        continue
    ans = 0
    while x >= k:
        ans += 1
        tmp = heappop(h)
        lst = []
        x -= 1
        for _ in range(k-1):
            s = heappop(h)
            s -= tmp
            if s == 0:
                x -= 1
                continue
            lst.append(s)
        for i in lst:
            heappush(h,i)
    print(ans)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
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()))


n = I()
a = LI()
c = list(Counter(a).items())

x = len(c)
H = []
for i,j in c:
    heappush(H,j)
for k in range(1,n+1):
    if k == 1:
        print(n)
        continue
    if k > x:
        print(0)
        continue
    h = H.copy()
    ans = 0
    while len(h) >= k:
        ans += 1
        tmp = heappop(h)
        lst = []
        for _ in range(k-1):
            s = heappop(h)
            s -= tmp
            if s == 0:
                continue
            lst.append(s)
        for i in lst:
            heappush(h,i)
    print(ans)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
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()))


n = I()
a = LI()
c = list(Counter(a).items())
x = len(c)
H = []
for i,j in c:
    heappush(H,-j)
for k in range(1,n+1):
    if k == 1:
        print(n)
        continue
    if k > x:
        print(0)
        continue
    h = H.copy()
    ans = 0
    while len(h) >= k:
        ans += 1
        tmp = heappop(h)
        tmp = -tmp
        lst = []
        for _ in range(k-1):
            s = heappop(h)  
            s = -s
            s -= tmp
            if s <= 0:
                continue
            lst.append(-s)
        for i in lst:
            heappush(h,i)
    print(ans)