Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
aaa = input()
bbb = input()
d = {}
ans = 'Yes'
for a, b in zip(aaa, bbb):
  if a in d and d.get(a) != b:
    print ('%s %s %s %s' % (aaa, bbb, a,b ))
    ans = 'No'
  d[a] = b
vs = list(d.values())
if max([vs.count(k) for k in vs]) >= 2:
  ans = 'No'
print(ans)

Fixed submission:
aaa = input()
bbb = input()
d = {}
d_rev = {}
ans = 'Yes'
for a, b in zip(aaa, bbb):
  if (a in d and d.get(a) != b) or (b in d_rev and d_rev.get(b) != a):
    ans = 'No'
  d[a] = b
  d_rev[b] = a
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math
N, M = list(map(int, input().split(' ')))
MOD = int(1e9 + 7)
primes = []
if M % 2 == 0:
  primes.append(2)
def is_prime(n):
  for i in range(len(primes)):
    if n % primes[i] == 0:
      return False
  return True
for i in range(3, int(1e5)):
  if is_prime(i):
    primes.append(i)

seeds = []
for p in primes:
  while M % p == 0:
    seeds.append(p)
    M = M // p

def comb(n, k):
  ans = 1
  for i in range(1, k + 1):
    ans = (ans * (n + 1 - i) // i)
  return ans

ans = comb(len(seeds)-1, N-1)
# !!! 24=(2^a1 * 3^b1) * (2^a2 * 3^b2) * ... | sum(a) = 3, sub(b) = 1, len(a) = 4
# aのパターン数は 3,0,0,0 = ooo|||, 2,1,0,0 = oo|o|| なので並び替えのパターン数で
# (sum(a) + 分ける数)! / (sum(a)! * 分ける数!) = (6!/(3!3!)) = 20
# b にも同じことをして 1,0,0,0 = o||| = (1+3)!/(1!*3!) = 4
# 24を4つに分けるパターンは 20 * 4 = 80?

# (a+b)!/(a!b!) = (a+b)Ca = (a+b)Cb

ans = 1
hogehoge = set(seeds)
for i in hogehoge:
  a_ct = seeds.count(i)
  ans = (ans * comb(a_ct + N-1, min(a_ct, N-1))) % MOD
print(ans)


Fixed submission:
N, M = list(map(int, input().split(' ')))
MOD = int(1e9 + 7)
primes = []
if M % 2 == 0:
  primes.append(2)

seeds = []
p = 2
while M > 1:
  while M % p == 0:
    seeds.append(p)
    M = M // p
  if p*p > M:
    if M != 1:
	    seeds.append(M)
    M = 0
  p += 1

def comb(n, k):
  ans = 1
  for i in range(1, k + 1):
    ans = (ans * (n + 1 - i) // i)
  return ans

ans = 1
hogehoge = set(seeds)
for i in hogehoge:
  a_ct = seeds.count(i)
  ans = (ans * comb(a_ct + N-1, min(a_ct, N-1))) % MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split(' ')))
l = list(map(int, input().split(' ')))
minuss = []
pluss = []
for i in l:
    if i < 0:
        minuss = [-i] + minuss
    else:
        pluss = pluss + [i]
minuss = [0] + minuss
pluss = [0] + pluss

# minuss から k本、plussからK-k本取る(短い方を折り返すので2倍)
ans = 1e9
for k in range(N):
    if k >= len(minuss) or K - k >= len(pluss):
        continue
    ans = min(ans, min(minuss[k] * 2 + pluss[K-k], minuss[k] + pluss[K-k] * 2))
print(ans)

Fixed submission:
N, K = list(map(int, input().split(' ')))
l = list(map(int, input().split(' ')))
minuss = [0] + [-i for i in l if i < 0][::-1]
pluss = [0] + [i for i in l if i >= 0]
# minuss から k本、plussからK-k本取る(短い方を折り返すので2倍)
ans = 1e16  # ?
if pluss == [0]:  # 4 2 [-4, -3 , -2, -1]
    pluss = minuss
    minuss = [0]
for k in range(K):
    if k >= len(minuss) or K - k >= len(pluss):
        continue
    ans = min(ans, min(minuss[k] * 2 + pluss[K-k], minuss[k] + pluss[K-k] * 2))
print(ans)
Buggy python submission (verdict: Runtime Error):
N, M = list(map(int, input().split(' ')))
edges = []
for i in range(M):
    a, b = list(map(int, input().split(' ')))
    edges.append([v for v in range(a, b)])

ans = 0
while any(edges):
    hit_index = 0
    max_hit = 0
    edge = []
    for i in range(len(edges)):
        if edges[i]:
            edge = edges[i]
            break
    for v in edge[::-1]:
        hit = 0
        for i in range(M):
            if edges[i] and v in edges[i]:
                hit += 1
            if hit > max_hit:
                max_hit = hit
                hit_index = v
    # print('max_hit')
    # print(max_hit)
    # print('cut here')
    # print(hit_index)
    for i in range(len(edges)):
        if edges[i] and hit_index in edges[i]:
            edges[i] = False
    ans += 1
    # print('cutted')
    # print(edges)
print(ans)


Fixed submission:
nums = sorted(list(map(int, input().split(' '))))
print(sum([abs(nums[i+1] - nums[i]) for i in range(len(nums) - 1)]))
Buggy python submission (verdict: Runtime Error):
a, b = raw_input()
return 'Yay!' if a <= 8 and b <= 8 else ':('

Fixed submission:
a, b = map(int, raw_input().split(' '))
print 'Yay!' if a <= 8 and b <= 8 else ':('
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())

mod = 1000000007

def pow(x, n):
    ret = 1
    while n > 0:
        if (n & 1) == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n //= 2
    return ret

def inv(n):
    return pow(n, mod - 2)

def fac(n):
    ret = 1
    for i in range(1, n + 1):
        ret = (ret * i) % mod
    return ret

def cmb(n, k):
    if k < 0 or k > n:
        return 0
    return (fac(n) * inv(fac(k)) * inv(fac(n - k))) % mod

x = max(0, n - k - 1)
ret = cmb(n * 2 - 1, n - 1)
for i in range(x):
    ret = (ret - cmb(n, i + 1) * cmb(n - 1, i)) % mod
print(ret)



Fixed submission:
n, k = map(int, input().split())

mod = 1000000007

def pow(x, n):
    ret = 1
    while n > 0:
        if (n & 1) == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n //= 2
    return ret

fac = [1]
inv = [1]
for i in range(n * 2):
    fac.append(fac[-1] * (i + 1) % mod)
    inv.append(pow(fac[-1], mod - 2))

def cmb(n, k):
    if k < 0 or k > n:
        return 0
    return (fac[n] * inv[k] * inv[n - k]) % mod

x = max(0, n - k - 1)
ret = cmb(n * 2 - 1, n - 1)
for i in range(x):
    ret = (ret - cmb(n, i + 1) * cmb(n - 1, i)) % mod
print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

n, k = map(int, input().split())
a = sorted(map(int, input().split()))

def count(t):
    c = 0
    for x in a:
        if x == 0:
            c += len(a) - 1 if t >= 0 else 0
        elif x > 0:
            c += bisect.bisect_right(a, (t // x)) - (x * x <= t)
        else:
            c += len(a) - bisect.bisect_left(a, -(t // -x)) - (x * x <= t)
    return c

lo = -1000000000000000001
hi = 1000000000000000001
while hi - lo > 1:
    mid = (lo + hi) // 2
    if count(mid) < k * 2:
        lo = mid
    else:
        hi = mid
print(hi)


Fixed submission:
import bisect

n, k = map(int, input().split())
a = sorted(map(int, input().split()))

def count(t):
    c = 0
    for x in a:
        if x == 0:
            c += len(a) - 1 if t >= 0 else 0
        elif x > 0:
            c += bisect.bisect_left(a, (t // x) + 1) - (x * x <= t)
        else:
            c += len(a) - bisect.bisect_left(a, -(t // -x)) - (x * x <= t)
    return c

lo = -1000000000000000001
hi = 1000000000000000001
while hi - lo > 1:
    mid = (lo + hi) // 2
    if count(mid) < k * 2:
        lo = mid
    else:
        hi = mid
print(hi)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

n, k = map(int, input().split())
a = sorted(map(int, input().split()))

def count(t):
    c = 0
    for x in a:
        if x == 0:
            c += len(a) - 1 if t >= 0 else 0
        elif x > 0:
            c += bisect.bisect_right(a, (t // x)) - (x * x <= t)
        else:
            c += len(a) - bisect.bisect_left(a, -(t // -x)) - (x * x <= t)
    return c

lo = -1000000000000000001
hi = 1000000000000000001
while hi - lo > 1:
    mid = (lo + hi) // 2
    if count(mid) < k * 2:
        lo = mid
    else:
        hi = mid
print(hi)


Fixed submission:
import bisect

n, k = map(int, input().split())
a = sorted(map(int, input().split()))

def count(t):
    c = 0
    for x in a:
        if x == 0:
            c += len(a) - 1 if t >= 0 else 0
        elif x > 0:
            c += bisect.bisect_left(a, (t // x) + 1) - (x * x <= t)
        else:
            c += len(a) - bisect.bisect_left(a, -(t // -x)) - (x * x <= t)
    return c

lo = -1000000000000000001
hi = 1000000000000000001
while hi - lo > 1:
    mid = (lo + hi) // 2
    if count(mid) < k * 2:
        lo = mid
    else:
        hi = mid
print(hi)
Buggy python submission (verdict: Runtime Error):
r1, c1, r2, c2 = map(int, input().split())

n = 200004
mod = 1000000007

def pow(x, n):
    ret = 1
    while n > 0:
        if (n & 1) == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n //= 2
    return ret

fac = [1]
inv = [1]
for i in range(1, n + 1):
    fac.append((fac[-1] * i) % mod)
    inv.append(pow(fac[i], mod - 2))

def cmb(n, k):
    if k < 0 or k > n:
        return 0
    return ((fac[n] * inv[k]) % mod * inv[n - k]) % mod

def rect(r, c):
    return cmb(r + c, c)

ret = (rect(r2 + 1, c2 + 1) - rect(r1, c2 + 1) - rect(r2 + 1, c1) + rect(r1, c1) + mod + mod) % mod
print(ret)


Fixed submission:
r1, c1, r2, c2 = map(int, input().split())

mod = 1000000007

def pow(x, n):
    ret = 1
    while n > 0:
        if (n & 1) == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n //= 2
    return ret

def fac(n):
    ret = 1
    for i in range(1, n + 1):
        ret = (ret * i) % mod
    return ret

def facinv(n):
    return pow(fac(n), mod - 2)

def cmb(n, k):
    if k < 0 or k > n:
        return 0
    return ((fac(n) * facinv(k)) % mod * facinv(n - k)) % mod

def rect(r, c):
    return cmb(r + c, c)

ret = (rect(r2 + 1, c2 + 1) - rect(r1, c2 + 1) - rect(r2 + 1, c1) + rect(r1, c1) + mod + mod) % mod
print(ret)

Buggy python submission (verdict: Runtime Error):
r1, c1, r2, c2 = map(int, input().split())

n = 200004
mod = 1000000007

def pow(x, n):
    ret = 1
    while n > 0:
        if (n & 1) == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n //= 2
    return ret

fac = [1]
inv = [1]
for i in range(1, n + 1):
    fac.append((fac[-1] * i) % mod)
    inv.append(pow(fac[i], mod - 2))

def cmb(n, k):
    if k < 0 or k > n:
        return 0
    return ((fac[n] * inv[k]) % mod * inv[n - k]) % mod

def rect(r, c):
    return cmb(r + c, c)

ret = (rect(r2 + 1, c2 + 1) - rect(r1, c2 + 1) - rect(r2 + 1, c1) + rect(r1, c1) + mod + mod) % mod
print(ret)


Fixed submission:
r1, c1, r2, c2 = map(int, input().split())

mod = 1000000007

def pow(x, n):
    ret = 1
    while n > 0:
        if (n & 1) == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n //= 2
    return ret

def fac(n):
    ret = 1
    for i in range(1, n + 1):
        ret = (ret * i) % mod
    return ret

def facinv(n):
    return pow(fac(n), mod - 2)

def cmb(n, k):
    if k < 0 or k > n:
        return 0
    return ((fac(n) * facinv(k)) % mod * facinv(n - k)) % mod

def rect(r, c):
    return cmb(r + c, c)

ret = (rect(r2 + 1, c2 + 1) - rect(r1, c2 + 1) - rect(r2 + 1, c1) + rect(r1, c1) + mod + mod) % mod
print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
dp = [0] + [10000000000] * h
ret = 10000000000
for i in range(h):
    for j in range(n):
        a, b = ab[j]
        if i + a >= h:
            ret = min(ret, dp[i] + b)
        else:
            dp[i + a] = min(dp[i + a], dp[i] + b)
print(ret)


Fixed submission:
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
dp = [0] + [10000000000] * h
ret = 10000000000
for i in range(h):
    for j in range(n):
        a, b = ab[j]
        if i + a >= h:
            ret = min(ret, dp[i] + b)
        else:
            dp[i + a] = min(dp[i + a], dp[i] + b)
print(ret)
Buggy python submission (verdict: Runtime Error):
h, w = map(int, input().split())
s = [input() for _ in range(h)]

def bfs(x, y):
    q = []
    dp = {}
    def qpush(x, y, t):
        if 0 <= x < w and 0 <= y < h and s[y][x] != '#' and (x, y) not in dp:
            q.append((x, y))
            dp[(x, y)] = t

    qpush(x, y, 0)
    while len(q) > 0:
        (x, y) = q.pop(0)
        qpush(x + 1, y, dp[(x, y)] + 1)
        qpush(x, y - 1, dp[(x, y)] + 1)
        qpush(x - 1, y, dp[(x, y)] + 1)
        qpush(x, y + 1, dp[(x, y)] + 1)
    return (dp[(x, y)], x, y)

(t, x, y) = bfs(0, 0)
(t, x, y) = bfs(x, y)
print(t)


Fixed submission:
h, w = map(int, input().split())
s = [input() for _ in range(h)]

def bfs(x, y):
    q = []
    dp = {}
    def qpush(x, y, t):
        if 0 <= x < w and 0 <= y < h and s[y][x] != '#' and (x, y) not in dp:
            q.append((x, y))
            dp[(x, y)] = t

    qpush(x, y, 0)
    while len(q) > 0:
        (x, y) = q.pop(0)
        qpush(x + 1, y, dp[(x, y)] + 1)
        qpush(x, y - 1, dp[(x, y)] + 1)
        qpush(x - 1, y, dp[(x, y)] + 1)
        qpush(x, y + 1, dp[(x, y)] + 1)
    return dp.get((x, y), 0)

t = 0
for y in range(h):
    for x in range(w):
        t = max(t, bfs(x, y))
print(t)
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
s = a[0]
t = 0
j = 1
ret = 0
for i in range(n):
    s -= a[i]
    ret += a[i] * 2
    m -= 1
    while j < n and (i >= n - 1 or a[i + 1] + a[i + 1] <= a[i] + a[j]):
        if m < i * 2:
            for k in range(i):
                if m > 0:
                    ret += a[j] + a[k]
                    m -= 1
                if m > 0:
                    ret += a[j] + a[k]
                    m -= 1
        else:
            ret += a[j] * i * 2 + t * 2
            m -= i * 2
        s += a[j]
        j += 1
    num = (j - i - 1) * 2
    if m <= num:
        for k in range(i + 1, j):
            if m > 0:
                ret += a[i] + a[k]
                m -= 1
            if m > 0:
                ret += a[i] + a[k]
                m -= 1
        break
    m -= num
    ret += s * 2 + a[i] * num
    t += a[i]
    print(a, m, num, s, i, j, ret)
print(ret)


Fixed submission:
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
s = [0]
for ai in a:
    s.append(ai + s[-1])

def count(x, accum=False):
    ret = 0
    for ai in a:
        lo, hi = -1, n
        while hi - lo > 1:
            mid = (lo + hi) // 2
            if ai + a[mid] >= x:
                lo = mid
            else:
                hi = mid
        ret += ai * hi + s[hi] if accum else hi
    return ret

lo, hi = 0, 1000000000
while hi - lo > 1:
    mid = (lo + hi) // 2
    if count(mid) >= m:
        lo = mid
    else:
        hi = mid

print(count(lo, accum=True) - (count(lo) - m) * lo)
Buggy python submission (verdict: Runtime Error):
n = int(input())
edges = [[] for _ in range(n)]
color = [0 for _ in range(n - 1)]
for e in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append((b - 1, e))
    edges[b - 1].append((a - 1, e))

def dfs(i, p, pcol):
    col = 1
    ret = 0
    for c, e in edges[i]:
        if c != p:
            if col == pcol:
                col += 1
            color[e] = col
            ret = max(ret, dfs(c, i, col))
            col += 1
    return max(ret, col - 1)

print(dfs(0, -1, -1))
for i in range(n - 1):
    print(color[i])

Fixed submission:
import sys

sys.setrecursionlimit(100000)

n = int(input())
edges = [[] for _ in range(n)]
color = [0 for _ in range(n - 1)]
for e in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append((b - 1, e))
    edges[b - 1].append((a - 1, e))

def dfs(i, p, pcol):
    col = 1
    ret = 0
    for c, e in edges[i]:
        if c != p:
            if col == pcol:
                col += 1
            color[e] = col
            ret = max(ret, dfs(c, i, col))
            col += 1
    return max(ret, col - 1)

print(dfs(0, -1, -1))
for i in range(n - 1):
    print(color[i])
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a = list(map(int, input().split()))
r = 0
s = {0: [0]}
for i in range(n):
    r = (r + a[i] - 1) % k
    s[r] = s.get(r, []) + [i + 1]
ret = 0
for key in s:
    a = s[key]
    en = 0
    for st in range(len(a)):
        while en < len(a) and a[en] - a[st] < k:
            en += 1
        ret += en - st - 1
print(ret)


Fixed submission:
n, k = map(int, input().split())
a = list(map(int, input().split()))
r = 0
s = {0: [0]}
for i in range(n):
    r = (r + a[i] - 1) % k
    if r in s:
        s[r].append(i + 1)
    else:
        s[r] = [i + 1]
ret = 0
for key in s:
    a = s[key]
    en = 0
    for st in range(len(a)):
        while en < len(a) and a[en] - a[st] < k:
            en += 1
        ret += en - st - 1
print(ret)

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a = list(map(int, input().split()))
r = 0
s = {0: [0]}
for i in range(n):
    r = (r + a[i] - 1) % k
    s[r] = s.get(r, []) + [i + 1]
ret = 0
for key in s:
    a = s[key]
    en = 0
    for st in range(len(a)):
        while en < len(a) and a[en] - a[st] < k:
            en += 1
        ret += en - st - 1
print(ret)


Fixed submission:
n, k = map(int, input().split())
a = list(map(int, input().split()))
r = 0
s = {0: [0]}
for i in range(n):
    r = (r + a[i] - 1) % k
    if r in s:
        s[r].append(i + 1)
    else:
        s[r] = [i + 1]
ret = 0
for key in s:
    a = s[key]
    en = 0
    for st in range(len(a)):
        while en < len(a) and a[en] - a[st] < k:
            en += 1
        ret += en - st - 1
print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
n, t = map(int, input().split())
ab = sorted(list(map(int, input().split())) for _ in range(n))
dp = [-1] * (t - 1) + [0]
ret = 0
for i in range(n):
    a, b = ab[i]
    newdp = dp[:]
    for j in range(t):
        if dp[j] >= 0:
            ret = max(ret, dp[j] + b)
            if j - a >= 0:
                newdp[j - a] = max(newdp[j - a], dp[j] + b)
    dp = newdp
print(ret)


Fixed submission:
n, t = map(int, input().split())
ab = sorted(list(map(int, input().split())) for _ in range(n))
dp = [-1] * (t - 1) + [0]
ret = 0
for i in range(n):
    a, b = ab[i]
    newdp = dp[:]
    for j in range(t):
        if dp[j] >= 0:
            ret = max(ret, dp[j] + b)
            if j - a >= 0:
                newdp[j - a] = max(newdp[j - a], dp[j] + b)
    dp = newdp
print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a = sorted(map(int, input().split()))
f = sorted(map(int, input().split()), reverse=True)

lo, hi = -1, 10 ** 19
while hi - lo > 1:
    mid = (lo + hi) // 2
    if sum(max(0, a - mid // f) for a, f in zip(a, f)) <= k:
        hi = mid
    else:
        lo = mid

print(hi)


Fixed submission:
n, k = map(int, input().split())
a = sorted(map(int, input().split()))
f = sorted(map(int, input().split()), reverse=True)

lo, hi = -1, 10 ** 18 + 1
while hi - lo > 1:
    mid = (lo + hi) // 2
    if sum(max(0, a[i] - mid // f[i]) for i in range(n)) <= k:
        hi = mid
    else:
        lo = mid

print(hi)
Buggy python submission (verdict: Time Limit Exceeded):
inf = 10 ** 13

n, m, l = map(int, input().split())

d = [[inf] * n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    d[a - 1][b - 1] = d[b - 1][a - 1] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

e = [[1 if d[i][j] <= l else inf for j in range(n)] for i in range(n)]
for k in range(n):
    for i in range(n):
        for j in range(n):
            e[i][j] = min(e[i][j], e[i][k] + e[k][j])

q = int(input())
for _ in range(q):
    s, t = map(int, input().split())
    a = e[s - 1][t - 1]
    print(a - 1 if a < inf else -1)


Fixed submission:
inf = 10 ** 13

n, m, l = map(int, input().split())

d = [[inf] * n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    d[a - 1][b - 1] = d[b - 1][a - 1] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

e = [[1 if d[i][j] <= l else inf for j in range(n)] for i in range(n)]
for k in range(n):
    for i in range(n):
        for j in range(n):
            e[i][j] = min(e[i][j], e[i][k] + e[k][j])

q = int(input())
for _ in range(q):
    s, t = map(int, input().split())
    a = e[s - 1][t - 1]
    print(a - 1 if a < inf else -1)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

n = int(input())
k = sorted(map(int, input().split()))

hist = []
count = 0
for i in range(n):
    count += 1
    if i == n - 1 or k[i] != k[i + 1]:
        hist.append(count)
        count = 0
hist.sort()

sumh = [0]
for i in range(len(hist)):
    sumh.append(sumh[-1] + hist[i])

def ok(h, d):
    i = bisect.bisect_left(hist, h)
    s = sumh[i] + h * (len(hist) - i)
    return s >= h * d

def binary_search(d):
    lo, hi = 0, 10 ** 10
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if ok(mid, d):
            lo = mid
        else:
            hi = mid
    return lo

for d in range(1, n + 1):
    print(binary_search(d))


Fixed submission:
import bisect

n = int(input())
k = sorted(map(int, input().split()))

hist = []
count = 0
for i in range(n):
    count += 1
    if i == n - 1 or k[i] != k[i + 1]:
        hist.append(count)
        count = 0
hist.sort()

sumh = [0]
for i in range(len(hist)):
    sumh.append(sumh[-1] + hist[i])

def ok(h, d):
    i = bisect.bisect_left(hist, h)
    s = sumh[i] + h * (len(hist) - i)
    return s >= h * d

def binary_search(d):
    lo, hi = 0, n // d + 1
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if ok(mid, d):
            lo = mid
        else:
            hi = mid
    return lo

for d in range(1, n + 1):
    print(binary_search(d))

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

n = int(input())
k = sorted(map(int, input().split()))

hist = []
count = 0
for i in range(n):
    count += 1
    if i == n - 1 or k[i] != k[i + 1]:
        hist.append(count)
        count = 0
hist.sort()

sumh = [0]
for i in range(len(hist)):
    sumh.append(sumh[-1] + hist[i])

def ok(h, d):
    i = bisect.bisect_left(hist, h)
    s = sumh[i] + h * (len(hist) - i)
    return s >= h * d

def binary_search(d):
    lo, hi = 0, 10 ** 10
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if ok(mid, d):
            lo = mid
        else:
            hi = mid
    return lo

for d in range(1, n + 1):
    print(binary_search(d))


Fixed submission:
import bisect

n = int(input())
k = sorted(map(int, input().split()))

hist = []
count = 0
for i in range(n):
    count += 1
    if i == n - 1 or k[i] != k[i + 1]:
        hist.append(count)
        count = 0
hist.sort()

sumh = [0]
for i in range(len(hist)):
    sumh.append(sumh[-1] + hist[i])

def ok(h, d):
    i = bisect.bisect_left(hist, h)
    s = sumh[i] + h * (len(hist) - i)
    return s >= h * d

def binary_search(d):
    lo, hi = 0, n // d + 1
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if ok(mid, d):
            lo = mid
        else:
            hi = mid
    return lo

for d in range(1, n + 1):
    print(binary_search(d))
Buggy python submission (verdict: Runtime Error):
n = input()
print((n // 2) / n)

Fixed submission:
n = float(input())
print((n - n // 2) / n)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
inf = 10 ** 9
dp = [0] + [inf] * ((1 << n) - 1)
for _ in range(m):
    newdp = [p for p in dp]
    a, b = map(int, input().split())
    c = sum(1 << (int(i) - 1) for i in input().split())
    for bits in range(len(dp)):
        newdp[bits | c] = min(newdp[bits | c], dp[bits] + a)
    dp = newdp
print(-1 if dp[-1] == inf else dp[-1])


Fixed submission:
n, m = map(int, input().split())
inf = 10 ** 9
dp = [0] + [inf] * ((1 << n) - 1)
for _ in range(m):
    newdp = [p for p in dp]
    a, b = map(int, input().split())
    c = sum(1 << (int(i) - 1) for i in input().split())
    for bits in range(len(dp)):
        newdp[bits | c] = min(newdp[bits | c], dp[bits] + a)
    dp = newdp
print(-1 if dp[-1] == inf else dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]
for i in range(n):
    print('Yes' if k + a.count(i + 1) - q > 0 else 'No')

Fixed submission:
n, k, q = map(int, input().split())
w = [0] * n
for i in range(q):
    w[int(input()) - 1] += 1
for i in range(n):
    print('Yes' if k + w[i] - q > 0 else 'No')