Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))


n = ni()
G = [list() for _ in range(n)]
for _ in range(n-1):
  a, b = nm()
  a -= 1; b -= 1
  G[a].append(b)
  G[b].append(a)
  
  
mod = 10**9 + 7
dub = [1]*(n+1)
for i in range(n):
  dub[i+1] = dub[i] * 2
  if dub[i+1] > mod:
    dub[i+1] -= mod
    
size = [1]*n
def dfs_depandsize(tree,v,p):
    for x in tree[v]:
        if x == p:
            continue
        size[v] += dfs_depandsize(tree,x,v)
    return size[v]
dfs_depandsize(G, 0, -1)
ans = 0
for v in range(n):
  c = 0
  res = 1
  for x in G[v]:
    if size[x] < size[v]:
      c += size[x]
      res += dub[size[x]] - 1
  res += dub[n-1-c] - 1
  res %= mod
  ans = (ans + dub[n-1] - res) % mod
print(ans * pow(dub[n], mod-2, mod) % mod)

Fixed submission:
import sys

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))


n = ni()
G = [list() for _ in range(n)]
for _ in range(n-1):
  a, b = nm()
  a -= 1; b -= 1
  G[a].append(b)
  G[b].append(a)
  
  
mod = 10**9 + 7
dub = [1]*(n+1)
for i in range(n):
  dub[i+1] = dub[i] * 2
  if dub[i+1] > mod:
    dub[i+1] -= mod
    
size = [-1]*n
q = [0]
while q:
  v = q[-1]
  if size[v] < 0:
    for x in G[v]:
      if size[x] < 0:
        q.append(x)
    size[v] = 0
  else:
    size[v] = 1
    for x in G[v]:
      size[v] += size[x]
    q.pop()

ans = 0
for v in range(n):
  c = 0
  res = 1
  for x in G[v]:
    if size[x] < size[v]:
      c += size[x]
      res += dub[size[x]] - 1
  res += dub[n-1-c] - 1
  res %= mod
  ans = (ans + dub[n-1] - res) % mod
print(ans * pow(dub[n], mod-2, mod) % mod)
Buggy python submission (verdict: Runtime Error):
def fold(x,m):
    y = 0
    for _ in range(m):
        if x & 1:
            y |= 1
        y <<= 1
        x >>= 1
    return x|y



h,w = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
b = [list(map(int, input().split())) for _ in range(h)]
g = [[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    g[i][j] = abs(a[i][j] - b[i][j])
a = b = 0
m = max(max(x) for x in g)
mask = (1<<(m*(h+w+2)//2)) - 1

dp = [[0]*(w+1) for _ in range(h+1)]
dp[0][1] = 1
dp[1][0] = 1
for i in range(1,h+1):
  for j in range(1,w+1):
    par = dp[i-1][j] | dp[i][j-1]
    dp[i][j] = mask&(par<<g[i-1][j-1])|fold(par,g[i-1][j-1])
for i in range(m*(h+w+2)//2):
  if dp[h][w]&(1<<i):
    print(i)
    break


Fixed submission:
n = int(input())
mod = 10**9 + 7
a = list(map(int, input().split()))
b = [sum(1 for x in a if x&(1<<i)) for i in range(60)]
ans = 0
for i in range(60):
  t = b[i]*(n-b[i])
  m = (1<<i)%mod
  ans = (ans + t*m%mod)%mod
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
mod = 10**9 + 7
a = list(map(int, input().split()))
b = [sum(1 for x in a if x&(1<<i)) for i in range(60)]
ans = 0
for i in range(60):
  t = b[i]*(n-b[i])
  m = (1<<i)%mod
  ans = (ans + t*m%mod)%mod
print(ans)

Fixed submission:
n = int(input())
mod = 10**9 + 7
a = list(map(int, input().split()))
b = [sum(1 for x in a if x&(1<<i)) for i in range(60)]
ans = 0
for i in range(60):
  t = b[i]*(n-b[i])
  m = (1<<i)%mod
  ans = (ans + t*m%mod)%mod
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def solve():
  n, x, d = nm()
  ans = 0
  if d == 0:
    print(0 if x == 0 else n)
  if d < 0:
    d = -d
    x = -x
  g = dict()
  g[0] = [(0, 0)]
  for i in range(1, n+1):
    c, y = divmod(x * i, d)
    # print((c, y))
    f = (c + i*(i-1)//2, c + n*i - i*(i+1)//2)
    if y not in g:
      g[y] = list()
    g[y].append(f)
  for y in g:
    f = sorted(g[y])
    # print(f)
    cx, cy = f[0]
    for nx, ny in f:
      if nx <= cy:
        cx = min(nx, cx)
        cy = max(ny, cy)
      else:
        ans += cy - cx + 1
        cx, cy = nx, ny
    ans += cy - cx + 1
  print(ans)
  return

solve()

Fixed submission:
import sys

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def solve():
  n, x, d = nm()
  ans = 0
  if d == 0:
    print(1 if x == 0 else n+1)
    return
  if d < 0:
    d = -d
    x = -x
  g = dict()
  g[0] = [(0, 0)]
  for i in range(1, n+1):
    c, y = divmod(x * i, d)
    # print((c, y))
    f = (c + i*(i-1)//2, c + n*i - i*(i+1)//2)
    if y not in g:
      g[y] = list()
    g[y].append(f)
  for y in g:
    f = sorted(g[y])
    # print(f)
    cx, cy = f[0]
    for nx, ny in f:
      if nx <= cy:
        cx = min(nx, cx)
        cy = max(ny, cy)
      else:
        ans += cy - cx + 1
        cx, cy = nx, ny
    ans += cy - cx + 1
  print(ans)
  return

solve()
Buggy python submission (verdict: Runtime Error):
for i in range(50001):
  if i*1.08//1 == n:
    print(i)
    break
else:
  print(":(")

Fixed submission:
n=int(input())
for i in range(50001):
  if i*1.08//1 == n:
    print(i)
    break
else:
  print(":(")
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()
cnt = 0
for i in range(1000):
  num = '{:03}'.format(i)
  t=0
  for j in range(n):
    if s[j] == num[t]:
      t += 1
      if t > 2:
        cnt += 1
        break
print(cnt)

Fixed submission:
n = int(input())
s = input()
cnt = 0
for i in range(1000):
  num = '{:03}'.format(i)
  t=0
  for j in range(n):
    if s[j] == num[t]:
      t += 1
      if t > 2:
        cnt += 1
        break
print(cnt)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int,input().split()))
for i in range(1,n):
    a[i] += a[i-1]
c = a[-1]
for i in range(n):
   p = abs(a[-1]-a[i]*2)
      if c > p:
        c = p   
print(c) 

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

for i in range(1,n):
    a[i] += a[i-1]

c = a[-1]
for i in range(n):
    c = min(c, abs(a[-1]-a[i]*2))
print(c)
Buggy python submission (verdict: Time Limit Exceeded):
m = int(input())
cnt = 0
res = None
for _ in range(m):
    d,c = map(int,input().split())
    while c:
        if c%2:
            if res is None:
                res = d
            else:
                res += d
                cnt += 1
                if res > 9:
                    res = res//10 + res%10
                    cnt += 1 
        d *= 2
        c //= 2
        cnt += c
        if d > 9:
            d = d//10 + d%10
            cnt += c
print(cnt)

Fixed submission:
m = int(input())
cnt = 0
res = None
for _ in range(m):
    d,c = map(int,input().split())
    while c:
        if c%2:
            if res is None:
                res = d
            else:
                res += d
                cnt += 1
                if res > 9:
                    res = res//10 + res%10
                    cnt += 1 
        d *= 2
        c //= 2
        cnt += c
        if d > 9:
            d = d//10 + d%10
            cnt += c
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
H = list(map(int, input().split())) + [0]
dp = [[10**12]*(K+2) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
  for j in range(min(i+1, K) + 1):
    for k in range(j + 1):
      dp[i+1][j] = min(dp[i+1][j], dp[i-k][j-k] + max(H[i] - H[i-k-1], 0))
ans = min(dp[-1])
for i in range(K):
  ans = min(ans, dp[N-i][K-i])
print(ans)

Fixed submission:
N, K = map(int, input().split())
H = list(map(int, input().split())) + [0]
dp = [[10**12]*(K+2) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
  for j in range(min(i+1, K) + 1):
    for k in range(j + 1):
      dp[i+1][j] = min(dp[i+1][j], dp[i-k][j-k] + max(H[i] - H[i-k-1], 0))
ans = min(dp[-1])
for i in range(K+1):
  ans = min(ans, dp[N-i][K-i])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
H = list(map(int, input().split())) + [0]
dp = [[10**14]*(K+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
  for j in range(min(i + 1, K) + 1):
    for k in range(j + 1):
      dp[i+1][j] = min(dp[i+1][j], dp[i-k][j-k] + max(H[i] - H[i-k-1], 0))
print(min(dp[-1]))

Fixed submission:
N, K = map(int, input().split())
H = list(map(int, input().split())) + [0]
dp = [[10**12]*(K+2) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
  for j in range(min(i+1, K) + 1):
    for k in range(j + 1):
      dp[i+1][j] = min(dp[i+1][j], dp[i-k][j-k] + max(H[i] - H[i-k-1], 0))
ans = min(dp[-1])
for i in range(K+1):
  ans = min(ans, dp[N-i][K-i])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
class SegTree:
    def __init__(self, N):
        self.N = N
        self._N = 1<<((N-1).bit_length())
        self.node = [10**15]*(2*self._N-1)
        self.node[self._N-1] = 0

    def eval(self,p):
        i = p + self._N-1
        cur = self.node[i]
        while i:
            i = (i-1) // 2
            if cur > self.node[i]:
                cur = self.node[i]
        self.node[p+self._N-1] = cur
        return cur

    def update(self,x,p,q,idx=0,a=0,b=None):
        if not idx:
            x += self.eval(p)
        if x >= 10**15:
            return
        if b is None:
            b = self._N
        if q <= p or b <= p or q <= a:
            return
        elif p <= a and b <= q:
            if x < self.node[idx]:
                self.node[idx] = x
            return
        else:
            self.update(x,p,q,idx*2+1,a,(a+b)//2)
            self.update(x,p,q,idx*2+2,(a+b)//2,b)
            return


n,m = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(m)]
edge.sort()
tr = SegTree(n)
for s,t,c in edge:
    tr.update(c,s-1,t)
ans = tr.eval(n-1)
if ans >= 10**15:
    ans = -1
print(ans)


Fixed submission:
class SegTree:
    def __init__(self, N):
        self.N = N
        self._N = 1<<((N-1).bit_length())
        self.node = [10**15]*(2*self._N-1)
        self.node[self._N-1] = 0

    def eval(self,p):
        i = p + self._N-1
        cur = self.node[i]
        while i:
            i = (i-1) // 2
            if cur > self.node[i]:
                cur = self.node[i]
        self.node[p+self._N-1] = cur
        return cur

    def update(self,x,p,q,idx=0,a=0,b=None):
        if not idx:
            x += self.eval(p)
        if x >= 10**15:
            return
        if b is None:
            b = self._N
        if q <= p or b <= p or q <= a:
            return
        elif p <= a and b <= q:
            if x < self.node[idx]:
                self.node[idx] = x
            return
        else:
            self.update(x,p,q,idx*2+1,a,(a+b)//2)
            self.update(x,p,q,idx*2+2,(a+b)//2,b)
            return


n,m = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(m)]
edge.sort()
tr = SegTree(n)
for s,t,c in edge:
    tr.update(c,s-1,t)
ans = tr.eval(n-1)
if ans >= 10**15:
    ans = -1
print(ans)
Buggy python submission (verdict: Runtime Error):
from math import atan, pi

a,b,v = map(int, input().split())
if v*2 < a*a*b:
  e= v*2/(a*b)
  theta = atan(e/b)
else:
  e = 2*(a*b - v/a)/a
  theta = atan(a/e)
theta *= 180/pi
print(90.0 - theta)

Fixed submission:
from math import atan, pi

a,b,v = map(int, input().split())
if v == a*a*b:
  theta = pi/2
elif v*2 < a*a*b:
  e= v*2/(a*b)
  theta = atan(e/b)
else:
  e = 2*(a*b - v/a)/a
  theta = atan(a/e)
theta *= 180/pi
print(90.0 - theta)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
a.sort(reverse=True)
f.sort()
z = list(zip(a,f))
ok = max(x*y for x,y in z)
ng = -1
while ok-ng>1:
  mid = (ok+ng)//2
  if sum(x-mid//y for x,y in z if x*y > mid) <= k:
    ok = mid
  else:
    ng = mid
print(ok)

Fixed submission:
n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
a.sort(reverse=True)
f.sort()
z = list(zip(a,f))
ok = max(x*y for x,y in z)
ng = -1
while ok-ng>1:
  mid = (ok+ng)//2
  if sum(x-mid//y for x,y in z if x*y > mid) <= k:
    ok = mid
  else:
    ng = mid
print(ok)

Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
a.sort(reverse=True)
f.sort()
z = list(zip(a,f))
ok = max(x*y for x,y in z)
ng = -1
while ok-ng>1:
  mid = (ok+ng)//2
  if sum(x-mid//y for x,y in z if x*y > mid) <= k:
    ok = mid
  else:
    ng = mid
print(ok)

Fixed submission:
n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
a.sort(reverse=True)
f.sort()
z = list(zip(a,f))
ok = max(x*y for x,y in z)
ng = -1
while ok-ng>1:
  mid = (ok+ng)//2
  if sum(x-mid//y for x,y in z if x*y > mid) <= k:
    ok = mid
  else:
    ng = mid
print(ok)

Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
a.sort(reverse=True)
f.sort()
ok = max(x*y for x,y in zip(a,f))
ng = -1

def judge(v):
  tot = 0
  for x,y in zip(a,f):
    if x*y > v:
      tot += x - v//y
  return tot <= k

while ok-ng>1:
  mid = (ok+ng)//2
  if judge(mid):
    ok = mid
  else:
    ng = mid
print(ok)

Fixed submission:
n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
a.sort(reverse=True)
f.sort()
z = list(zip(a,f))
ok = max(x*y for x,y in z)
ng = -1
while ok-ng>1:
  mid = (ok+ng)//2
  if sum(x-mid//y for x,y in z if x*y > mid) <= k:
    ok = mid
  else:
    ng = mid
print(ok)
Buggy python submission (verdict: Time Limit Exceeded):
nm = lambda : map(int,input().split())
nl = lambda : list(nm())

import bisect

n = int(input())
l = nl()
l.sort()
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        a,b = l[i],l[j]
        if a > b:
            a,b = b,a
        lef = bisect.bisect_right(l,b-a)
        rig = bisect.bisect_left(l,a+b)
        t = rig - lef - 1 - (b < 2*a)
        ans += t
print(ans//3)

Fixed submission:
nm = lambda : map(int,input().split())
nl = lambda : list(nm())

import bisect

n = int(input())
l = nl()
l.sort()
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        a,b = l[i],l[j]
        if a > b:
            a,b = b,a
        lef = bisect.bisect_right(l,b-a)
        rig = bisect.bisect_left(l,a+b)
        t = rig - lef - 1 - (b < 2*a)
        ans += t
print(ans//3)
Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())
dp = [10**9]*(2**n)
for i in range(m):
  a,_ = map(int,input().split())
  c = list(map(int,input().split()))
  t = 0
  for x in c:
    t |= 1<<(x-1)
  for b in range(2**n):
    dp[b|t] = min(dp[b],dp[b+a])
if dp[-1] > 10**8:
  print(-1)
else:
  print(dp[-1])

Fixed submission:
n,m = map(int,input().split())
dp = [10**9]*(2**n)
dp[0] = 0
for _ in range(m):
  a,_ = map(int,input().split())
  c = list(map(int,input().split()))
  t = 0
  for x in c:
    t |= 1<<(x-1)
  for b in range(2**n):
    dp[b|t] = min(dp[b|t],dp[b]+a)
if dp[-1] > 10**8:
  print(-1)
else:
  print(dp[-1])
Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())
raw = list(map(int,input().split()))
num = 2**(n-1).bit_length()
seg1 = [0]*2*num
seg2 = [n]*2*num

def build(raw):
    for i in range(n):
        seg1[i+num-1] = raw[i]
        seg2[i+num-1] = raw[i]
    for i in range(num-2,-1,-1):
        seg1[i] = max(seg1[2*i+1],seg1[2*i+2])
        seg2[i] = min(seg2[2*i+1],seg2[2*i+2])
    return True

build(raw)
cnt = n-k+1

def query(seg,ele,segf,p,q):
    if q <= p:
        return False
    p += num - 1
    q += num - 2
    res = ele
    while q-p > 1:
        if not p%2:
            res = segf(res,seg[p])
        if q%2:
            res = segf(res,seg[q])
            q -= 1
        p //= 2
        q = (q-1)//2
    if p == q:
        res = segf(res,seg[p])
    else:
        res = segf(res,seg[p],seg[q])
    return res

def check(i):
    #print(i,query(seg1,0,max,i,i+k+1),query(seg2,n+1,min,i,i+k+1))
    return query(seg1,0,max,i,i+k+1) == raw[i+k] and query(seg2,n+1,min,i,i+k+1) == raw[i]

t = [0]*n
f = -1
c = -1
for i in range(n):
    if raw[i] > c:
        f += 1
    else:
        f = 0
    c = raw[i]
    t[i] = f

for i in range(n-k):
    if t[i+k-1] - t[i] == k-1 or check(i):
        #print("y")
        cnt -= 1
print(cnt)

Fixed submission:
h,w,a,b = map(int,input().split())
if b > h//2 or a > w//2:
    print("No")
    exit(0)
for _ in range(h-b):
    print("0"*(w-a) + "1"*a)
for _ in range(b):
    print("1"*(w-a) + "0"*a)
Buggy python submission (verdict: Time Limit Exceeded):
def Z(s):
    ls = len(s)
    lcp = [0]*ls
    lcp[0] = ls
    i,j = 1,0
    while i < ls:
        while i+j < ls and s[j] == s[i+j]:
            j += 1
        lcp[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < ls and k + lcp[k] < j:
            lcp[i+k] = lcp[k]
            k += 1
        i += k
        j -= k
    for i in range(ls):
        lcp[i] = min(lcp[i],i)
    return max(lcp)

n = int(input())
s = input()
print(max(Z(s[i:]) for i in range(n)))

Fixed submission:
def Z(s,ls):
    lcp = [0]*ls
    lcp[0] = ls
    i,j = 1,0
    while i < ls:
        while i+j < ls and s[j] == s[i+j]:
            j += 1
        lcp[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < ls and k + lcp[k] < j:
            lcp[i+k] = lcp[k]
            k += 1
        i += k
        j -= k
    for i in range(ls):
        lcp[i] = min(lcp[i],i)
    return max(lcp)

n = int(input())
s = list(map(ord,list(input())))
print(max(Z(s[i:],n-i) for i in range(n)))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
n = int(input())
a = sorted(Counter(list(map(int, input().split()))).items(), reverse=True)
if len(a) == 2 ** n:
  print('Yes')
  exit(0)
g = [0]*(n+1)
g[n] = 1
for _, x in a:
  if sum(g) < x:
    print('No')
    break
  t = [0]*(n+1)
  for i in range(n, -1, -1):
    if g[i] <= x:
      t[i-1] = t[i] + g[i]
      x -= g[i]
      g[i] = 0
    else:
      t[i-1] = t[i] + x
      g[i] -= x
      x = 0
  t[n] = 0
  g = [x+y for x,y in zip(g, t)]
else:
  print('Yes')


Fixed submission:
from collections import Counter
n = int(input())
a = sorted(Counter(list(map(int, input().split()))).items(), reverse=True)
g = [0]*(n+1)
g[n] = 1
for _, x in a:
  if sum(g) < x:
    print('No')
    break
  t = [0]*(n+1)
  for i in range(n, -1, -1):
    if g[i] <= x:
      t[i-1] = t[i] + g[i]
      x -= g[i]
      g[i] = 0
    else:
      t[i-1] = t[i] + x
      g[i] -= x
      x = 0
  t[n] = 0
  g = [x+y for x,y in zip(g, t)]
else:
  print('Yes')

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

def main():
  n = int(input())
  a = sorted(Counter(list(map(int, input().split()))).items(), reverse=True)
  g = [0]*(n+1)
  g[n] = 1
  for _, x in a:
    if sum(g) < x:
      print('No')
      break
    t = [0]*(n+1)
    for i in range(n, -1, -1):
      if g[i] <= x:
        t[i-1] = t[i] + g[i]
        x -= g[i]
        g[i] = 0
      else:
        t[i-1] = t[i] + x
        g[i] -= x
        x = 0
      t[i] += g[i]
    t[n] = 0
    g = t
  else:
    print('Yes')
  return

if __name__ == '__main__':
  main()

Fixed submission:
from collections import Counter
n = int(input())
a = sorted(Counter(list(map(int, input().split()))).items(), reverse=True)
g = [0]*(n+1)
g[n] = 1
for _, x in a:
  if sum(g) < x:
    print('No')
    break
  t = [0]*(n+1)
  for i in range(n, -1, -1):
    if g[i] <= x:
      t[i-1] = t[i] + g[i]
      x -= g[i]
      g[i] = 0
    else:
      t[i-1] = t[i] + x
      g[i] -= x
      x = 0
  t[n] = 0
  g = [x+y for x,y in zip(g, t)]
else:
  print('Yes')

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
n = int(input())
a = sorted(Counter(list(map(int, input().split()))).items(), reverse=True)
g = [0]*(n+1)
g[n] = 1
for _, x in a:
  if sum(g) < x:
    print('No')
    break
  t = [0]*(n+1)
  for i in range(n, -1, -1):
    if g[i] <= x:
      t[i-1] = t[i] + g[i]
      x -= g[i]
      g[i] = 0
    else:
      t[i-1] = t[i] + x
      g[i] -= x
      x = 0
  t[n] = 0
  g = [x+y for x,y in zip(g, t)]
else:
  print('Yes')

Fixed submission:
from collections import Counter
n = int(input())
a = sorted(Counter(list(map(int, input().split()))).items(), reverse=True)
g = [0]*(n+1)
g[n] = 1
for _, x in a:
  if sum(g) < x:
    print('No')
    break
  t = [0]*(n+1)
  for i in range(n, -1, -1):
    if g[i] <= x:
      t[i-1] = t[i] + g[i]
      x -= g[i]
      g[i] = 0
    else:
      t[i-1] = t[i] + x
      g[i] -= x
      x = 0
  t[n] = 0
  g = [x+y for x,y in zip(g, t)]
else:
  print('Yes')
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
t = 0
f = 1
cur = [0]*(n+1)
while f:
    f = 0
    done = [0]*(n+1)
    for i in range(1,n+1):
        if done[i] or cur[i] == n-1:
            continue
        op = a[i-1][cur[i]]
        if a[op-1][cur[op]] == i and not done[op]:
            cur[i] += 1
            cur[op] += 1
            done[i] = 1
            done[op] = 1
            f = 1
    if f:
      t += 1
if any([x<n-1 for x in cur[1:]]):
    print(-1)
else:
    print(t)

Fixed submission:
from collections import deque

n = int(input())
a = ["dummy!"] + [list(map(int, input().split())) for _ in range(n)]
t = 0
f = 1
cur = [0]*(n+1)
date = [0]*(n+1)
seed = deque()
for i in range(1,n+1):
    op = a[i][cur[i]]
    if a[op][cur[op]] == i:
        seed.append((i,op))
        cur[i] += 1
        cur[op] += 1
        date[i] = date[op] = max(date[i],date[op]) + 1
while seed:
    p,q = seed.popleft()   
    for i in p,q:
        if cur[i] >= n-1:
            continue
        op = a[i][cur[i]]
        if a[op][cur[op]] == i:
            seed.append((i,op))
            cur[i] += 1
            cur[op] += 1
            date[i] = date[op] = max(date[i],date[op]) + 1
if any(x < n-1 for x in cur[1:]):
    print(-1)
else:
    print(max(date))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
t = 0
f = 1
cur = [0]*(n+1)
while f:
    f = 0
    done = [0]*(n+1)
    for i in range(1,n+1):
        if done[i] or cur[i] == n-1:
            continue
        op = a[i-1][cur[i]]
        if a[op-1][cur[op]] == i and not done[op]:
            cur[i] += 1
            cur[op] += 1
            done[i] = 1
            done[op] = 1
            f = 1
    if f:
      t += 1
if any([x<n-1 for x in cur[1:]]):
    print(-1)
else:
    print(t)

Fixed submission:
from collections import deque

n = int(input())
a = ["dummy!"] + [list(map(int, input().split())) for _ in range(n)]
t = 0
f = 1
cur = [0]*(n+1)
date = [0]*(n+1)
seed = deque()
for i in range(1,n+1):
    op = a[i][cur[i]]
    if a[op][cur[op]] == i:
        seed.append((i,op))
        cur[i] += 1
        cur[op] += 1
        date[i] = date[op] = max(date[i],date[op]) + 1
while seed:
    p,q = seed.popleft()   
    for i in p,q:
        if cur[i] >= n-1:
            continue
        op = a[i][cur[i]]
        if a[op][cur[op]] == i:
            seed.append((i,op))
            cur[i] += 1
            cur[op] += 1
            date[i] = date[op] = max(date[i],date[op]) + 1
if any(x < n-1 for x in cur[1:]):
    print(-1)
else:
    print(max(date))