Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
class Union:
  def __init__(self, num):
    self.T = [-1 for i in range(num)]

  def root(self, x):
    if self.T[x] < 0: return x
    return self.root(self.T[x])

  def size(self, x):
    return -self.T[self.root(x)]

  def merge(self, x, y):
    a = self.root(x)
    b = self.root(y)
    if a == b: return False
    if self.size(a) < self.size(b): a, b = b, a
    self.T[a] += self.T[b]
    self.T[b] = a
    return True

  def same(self, x, y):
    return self.root(x) == self.root(y)


N, M, K = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

uni = Union(N)
f = [0] * N
for a, b in AB:
  a -= 1
  b -= 1
  uni.merge(a, b)
  f[a] += 1
  f[b] += 1

L = [[] for _ in range(N)]
for c, d in CD:
  c -= 1
  d -= 1
  L[c].append(d)
  L[d].append(c)

ans = [0] * N

for i in range(N):
  k = uni.size(i)
  k -= f[i] + 1
  for j in L[i]:
    if uni.same(i, j):
      k -= 1
  ans[i] = k

ans = map(str, ans)
print(" ".join(ans))

Fixed submission:
class Union:
  def __init__(self, num):
    self.T = [-1 for i in range(num)]

  def root(self, x):
    if self.T[x] < 0: return x
    return self.root(self.T[x])

  def size(self, x):
    return -self.T[self.root(x)]

  def merge(self, x, y):
    a = self.root(x)
    b = self.root(y)
    if a == b: return False
    if self.size(a) < self.size(b): a, b = b, a
    self.T[a] += self.T[b]
    self.T[b] = a
    return True

  def same(self, x, y):
    return self.root(x) == self.root(y)

import sys
input = sys.stdin.readline
N, M, K = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

uni = Union(N)
ans = [-1] * N
for a, b in AB:
  a -= 1
  b -= 1
  uni.merge(a, b)
  ans[a] -= 1
  ans[b] -= 1

L = [[] for _ in range(N)]
for c, d in CD:
  c -= 1
  d -= 1
  L[c].append(d)
  L[d].append(c)

for i in range(N):
  ans[i] += uni.size(i)
  for j in L[i]:
    if uni.same(i, j):
      ans[i] -= 1

ans = map(str, ans)
print(" ".join(ans))
Buggy python submission (verdict: Time Limit Exceeded):
class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD


r1, c1, r2, c2 = list(map(int, input().split()))
MOD = 10 ** 9 + 7

def nasu(n, m):
  ans = (com.com(n + 2, m + 1) - 1)
  return ans
N = r2 + c2
com = comb(N + 3, MOD)

ans = nasu(N, r2)
ans = (ans + nasu(c1 + r1 - 2, min(c1, r1) - 1)) % MOD
ans = (ans - nasu(r2 + c1 - 1, c1 - 1))
ans = (ans - nasu(c2 + r1 - 1, r1 - 1))
while ans < 0: ans += MOD

print(ans)

Fixed submission:
class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD


r1, c1, r2, c2 = list(map(int, input().split()))
MOD = 10 ** 9 + 7

def nasu(n, m):
  if n < 0 or m < 0: return 0
  ans = (com.com(n + 2, m + 1) - 1)
  return ans
N = r2 + c2
com = comb(N + 3, MOD)

ans = nasu(N, r2)
ans = (ans + nasu(c1 + r1 - 2, min(c1, r1) - 1)) % MOD
ans = (ans - nasu(r2 + c1 - 1, c1 - 1))
ans = (ans - nasu(c2 + r1 - 1, r1 - 1))
while ans < 0: ans += MOD

print(ans)
Buggy python submission (verdict: Runtime Error):
H, N = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

inf = 10 ** 10
DP = [[inf] * (H + 1) for _ in range(N)]

for i in range(N):
  a, b = AB[i]
  for j in range(1, a + 1):
    if i == 0:
      DP[i][j] = b
    else:
      DP[i][j] = min(DP[i - 1][j], b)
  for j in range(a + 1, H + 1):
    if i == 0:
      DP[i][j] = DP[i][j - a] + b
    else:
      DP[i][j] = min(DP[i - 1][j], DP[i][j - a] + b)

print(DP[-1][H])



Fixed submission:
H, N = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

inf = 10 ** 10
DP = [[inf] * (H + 1) for _ in range(N)]

for i in range(N):
  a, b = AB[i]
  if a >= H:
    for j in range(H + 1):
      if i == 0:
        DP[i][j] = b
      else:
        DP[i][j] = min(DP[i - 1][j], b)
    continue
  for j in range(1, a + 1):
    if i == 0:
      DP[i][j] = b
    else:
      DP[i][j] = min(DP[i - 1][j], b)
  for j in range(a + 1, H + 1):
    if i == 0:
      DP[i][j] = DP[i][j - a] + b
    else:
      DP[i][j] = min(DP[i - 1][j], DP[i][j - a] + b)

print(DP[-1][H])
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

def gcd(x, y):
  b = max(x, y)
  s = min(x, y)
  r = b % s
  while r != 0:
    b = s
    s = r
    r = b % s
  return s

def lcm(x, y):
  return (x * y) // gcd(x,y)

class Inv:
  def __init__(s, mod):
    s.MOD = mod
  def modpow(s, a, n):
    res = 1
    while n > 0:
      if n & 1:
        res = res * a % s.MOD
      a = a * a % s.MOD
      n >>= 1
    return res
  def invx(s, a):
    return s.modpow(a, s.MOD - 2)
  def invL(s, a, n):
    ia = s.invx(a)
    L = [1] * (n + 1)
    for i in range(1, n + 1):
      L[i] = L[i - 1] * ia % s.MOD
    return L

t = lcm(A[0], A[1])
inv = Inv(MOD)
for i in range(2, N):
  t = lcm(t, A[i]) % MOD

ans = 0
for i in range(N):
  ans = (ans + t * inv.invx(A[i])) % MOD
print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

if N == 1:
  print(1)
  exit()

import math
def prime(x):
  p = {}
  cnt = 2
  Flag = True
  while Flag:
    last = math.ceil(x ** 0.5) 
    if cnt > last:
      break
    for i in range(cnt, last + 1):
      if x % i == 0:
        x //= i
        p[i] = 1
        cnt = i + 2
        while x % i == 0:
          x //= i
          p[i] += 1
        cnt = i + 1
        break
      if i == last:
        Flag = False
  if x != 1:
    p[x] = 1
  return p


class Inv:
  def __init__(s, mod):
    s.MOD = mod
  def modpow(s, a, n):
    res = 1
    while n > 0:
      if n & 1:
        res = res * a % s.MOD
      a = a * a % s.MOD
      n >>= 1
    return res
  def invx(s, a):
    return s.modpow(a, s.MOD - 2)
  def invL(s, a, n):
    ia = s.invx(a)
    L = [1] * (n + 1)
    for i in range(1, n + 1):
      L[i] = L[i - 1] * ia % s.MOD
    return L

p = prime(A[0])

for i in range(1, N):
  q = prime(A[i])
  for n in q:
    if n in p:
      p[n] = max(p[n], q[n])
    else:
      p[n] = q[n]

inv = Inv(MOD)
t = 1
for n in p:
  t = t * inv.modpow(n, p[n]) % MOD

ans = 0
for i in range(N):
  ans = (ans + t * inv.invx(A[i])) % MOD
print(ans)
Buggy python submission (verdict: Runtime Error):
H, W = list(map(int, input().split()))
S = [list(input()) for _ in range(H)]
import queue
import copy
class gridMan:
  def __init__(s, L):
    s.L = L
  def makeWall(s, x):
    w = len(s.L[0]) + 2
    s.L = [[x] * w] + [[x] + i + [x] for i in s.L] + [[x] * w]
  def dist(s, S, G):
    T = copy.deepcopy(s.L)

    T[S[0] + 1][S[1] + 1] = 1
    q = queue.Queue()
    q.put([S[0] + 1, S[1] + 1])
    while not q.empty():
      h, w = q.get()
      k = T[h][w]
      for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        hh = h + i
        ww = w + j
        if T[hh][ww] == -1:
          continue
        t = T[hh][ww]
        if t == 0:
          q.put([hh, ww])
          T[hh][ww] = k + 1
    return T[G[0] + 1][G[1] + 1] - 1

for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      S[i][j] = -1
    else:
      S[i][j] = 0

g = gridMan(S)
g.makeWall(-1)
ans = 0
for sx in range(H):
  for sy in range(W):
    if S[sx][sy] == -1:
      continue
    for gx in range(sx, H):
      for gy in range(W):
        if S[sx][sy] == -1:
          continue
        if sx == gx and sy == gy: continue
        ans = max(ans, g.dist([sx, sy], [gx, gy]))

g.dist([0, 0], [2, 2])
print(ans)

Fixed submission:
H, W = list(map(int, input().split()))
S = [list(input()) for _ in range(H)]
import queue
import copy
class gridMan:
  def __init__(s, L):
    s.L = L
  def makeWall(s, x):
    w = len(s.L[0]) + 2
    s.L = [[x] * w] + [[x] + i + [x] for i in s.L] + [[x] * w]
  def dist(s, S):
    T = copy.deepcopy(s.L)
    T[S[0] + 1][S[1] + 1] = 1
    q = queue.Queue()
    q.put([S[0] + 1, S[1] + 1])
    ans = 0
    while not q.empty():
      h, w = q.get()
      k = T[h][w]
      ans = max(ans, k)
      for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        hh = h + i
        ww = w + j
        if T[hh][ww] == -1:
          continue
        t = T[hh][ww]
        if t == 0:
          q.put([hh, ww])
          T[hh][ww] = k + 1
    return ans - 1

for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      S[i][j] = -1
    else:
      S[i][j] = 0

g = gridMan(S)
g.makeWall(-1)
ans = 0
for sx in range(H):
  for sy in range(W):
    if S[sx][sy] == -1:
      continue
    ans = max(ans, g.dist([sx, sy]))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
H, W = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
M = 6401


D = [[0] * W for _ in range(H)]
for i in range(H):
  for j in range(W):
    D[i][j] = abs(B[i][j] - A[i][j])

DP = [[[0] * M for _ in range(W)] for _ in range(H)]

def nasu(t):
  if t >= 0 and t < M:
    return True
  else:
    return False

DP[0][0][D[0][0]] = 1
for i in range(H + W):
  for j in range(H):
    if i - j >= W: continue
    x = i - j
    y = j
    if x < 0: continue
    if x - 1 >= 0:
      for k in range(M):
        if DP[y][x - 1][k] == 1:
          t = k + D[y][x]
          if nasu(t):
            DP[y][x][t] = 1
          t = abs(k - D[y][x])
          if nasu(t):
            DP[y][x][t] = 1
    if y - 1 >= 0:
      for k in range(M):
        if DP[y - 1][x][k] == 1:
          t = k + D[y][x]
          if nasu(t):
            DP[y][x][t] = 1
          t = abs(k - D[y][x])
          if nasu(t):
            DP[y][x][t] = 1

for i in range(M):
  if DP[-1][-1][i] == 1:
    print(i)
    break

Fixed submission:
H, W = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
M = 6401

def honya(y, d):
  t = (1 << d + 1) - 1
  t = y & t
  k = 0
  for i in range(d):
    k += t & 1
    t >>= 1
    k <<= 1
  return k

D = [[0] * W for _ in range(H)]
for i in range(H):
  for j in range(W):
    D[i][j] = abs(B[i][j] - A[i][j])

DP = [[0] * W for _ in range(H)]

def nasu(x, y, d):
  t = (1 << (d + 1)) - 1 & y
  return (x | (y << d) | (y >> d) | honya(y, d)) & mask
  

mask = (1 << M) - 1
DP[0][0] = 1 << D[0][0]
for i in range(H):
  for j in range(W):
    if i + 1 < H:
      DP[i + 1][j] = nasu(DP[i + 1][j], DP[i][j], D[i + 1][j])
    if j + 1 < W:
      DP[i][j + 1] = nasu(DP[i][j + 1], DP[i][j], D[i][j + 1])

t = DP[-1][-1]
for i in range(M):
  if t & 1:
    print(i)
    break
  t >>= 1
Buggy python submission (verdict: Runtime Error):
N, X, D = list(map(int, input().split()))

R = {}
R[0] = [[0, 0]]
d, m, l, r = 0, 0, 0, 0

for i in range(N):
  d += (m + X) // D
  m = (m + X) % D
  l += i
  r += N - i - 1
  if m not in R:
    R[m] = [[d + l, d + r]]
  else:
    R[m].append([d + l, d + r])
  
ans = 0
for i in R:
  t = R[i]
  t.sort()
  l, r = t[0]
  for j in range(1, len(t)):
    if r < t[j][0]:
      ans += abs(r - l) + 1
      l, r = t[j]
    else:
      r = t[j][1]
  ans += abs(r - l) + 1

print(ans)

Fixed submission:
N, X, D = list(map(int, input().split()))

if D == 0:
  if X == 0:
    print(1)
  else:
    print(N + 1)
  exit()

if D < 0:
  D *= -1
  X *= -1

R = {}
R[0] = [[0, 0]]
d, m, l, r = 0, 0, 0, 0

for i in range(N):
  d += (m + X) // D
  m = (m + X) % D
  l += i
  r += N - i - 1
  if m not in R:
    R[m] = [[d + l, d + r]]
  else:
    R[m].append([d + l, d + r])
  
ans = 0
for i in R:
  t = R[i]
  t.sort()
  l, r = t[0]
  for j in range(1, len(t)):
    if r < t[j][0]:
      ans += abs(r - l) + 1
      l, r = t[j]
    else:
      r = max(r, t[j][1])
  ans += abs(r - l) + 1

print(ans)
Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

L = [-1] * N
D = [0] * K
D[A[0] % K] = 1
t = A[0] % K
L[0] = t
for i in range(1, min(K - 1, N)):
  t = (t + A[i] - 1) % K
  if t < 0:
    t += K
  D[t] += 1
  L[i] = t

n = 1
ans = D[n]
for i in range(N):
  if L[i] != -1:
    D[L[i]] -= 1
  if i + K - 1 < N:
    t = (t + A[i + K - 1] - 1) % K
    if t < 0:
      t += K
    D[t] += 1
    L[i + K - 1] = t
  n = (n - 1 + A[i]) % K
  #n -= 1
  if n < 0:
    n += K
  ans += D[n]
  
print(ans)

Fixed submission:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

if K == 1:
  print(0)
  exit()

L = [-1] * N
D = {}
D[A[0] % K] = 1
t = A[0] % K
L[0] = t
for i in range(1, min(K - 1, N)):
  t = (t + A[i] - 1) % K
  if t < 0:
    t += K
  if t in D:
    D[t] += 1
  else:
    D[t] = 1
  L[i] = t

n = 1
if n in D:
  ans = D[n]
else:
  ans = 0
for i in range(N):
  if L[i] != -1:
    D[L[i]] -= 1
  if i + K - 1 < N:
    t = (t + A[i + K - 1] - 1) % K
    if t < 0:
      t += K
    if t in D:
      D[t] += 1
    else:
      D[t] = 1
    L[i + K - 1] = t
  n = (n - 1 + A[i]) % K
  #n -= 1
  if n < 0:
    n += K
  if n in D:
    ans += D[n]
  
print(ans)

Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

L = [-1] * N
D = [0] * K
D[A[0] % K] = 1
t = A[0] % K
L[0] = t
for i in range(1, min(K - 1, N)):
  t = (t + A[i] - 1) % K
  if t < 0:
    t += K
  D[t] += 1
  L[i] = t

n = 1
ans = D[n]
for i in range(N):
  if L[i] != -1:
    D[L[i]] -= 1
  if i + K - 1 < N:
    t = (t + A[i + K - 1] - 1) % K
    if t < 0:
      t += K
    D[t] += 1
    L[i + K - 1] = t
  n = (n - 1 + A[i]) % K
  #n -= 1
  if n < 0:
    n += K
  ans += D[n]
  
print(ans)

Fixed submission:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

if K == 1:
  print(0)
  exit()

L = [-1] * N
D = {}
D[A[0] % K] = 1
t = A[0] % K
L[0] = t
for i in range(1, min(K - 1, N)):
  t = (t + A[i] - 1) % K
  if t < 0:
    t += K
  if t in D:
    D[t] += 1
  else:
    D[t] = 1
  L[i] = t

n = 1
if n in D:
  ans = D[n]
else:
  ans = 0
for i in range(N):
  if L[i] != -1:
    D[L[i]] -= 1
  if i + K - 1 < N:
    t = (t + A[i + K - 1] - 1) % K
    if t < 0:
      t += K
    if t in D:
      D[t] += 1
    else:
      D[t] = 1
    L[i + K - 1] = t
  n = (n - 1 + A[i]) % K
  #n -= 1
  if n < 0:
    n += K
  if n in D:
    ans += D[n]
  
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse = True)

import heapq
pop = heapq.heappop
push = heapq.heappush
q  = []

for i in range(N):
  push(q, [- A[i] * F[i], A[i], F[i]])

for i in range(K):
  x, y, z = pop(q)
  if y == 0:
    print(0)
    exit()
  push(q, [- (y - 1) * z, y - 1, z])

t = pop(q)
print(-t[0])

Fixed submission:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse = True)

M = 0
for i in range(N):
  M += A[i] * F[i]

def nasu(n):
  ans = 0
  for i in range(N):
    ans += max(0, A[i] - (n // F[i]))
  if ans <= K:
    return True
  else:
    return False

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

print(hersCode())
Buggy python submission (verdict: Time Limit Exceeded):
import sys

N, M, L = list(map(int, input().split()))
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
Q = int(input())
st = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

D = [[0] * N for _ in range(N)]
R = {}

for a, b, c in ABC:
  a -= 1
  b -= 1
  D[a][b] = c
  D[b][a] = c
  if a not in R:
    R[a] = [[b, c]]
  else:
    R[a].append([b, c])
  if b not in R:
    R[b] = [[a, c]]
  else:
    R[b].append([a, c])

inf = 10 ** 10
T = [[inf] * N for _ in range(N)]
import copy
for i in range(N):
  if i not in R: continue
  S = copy.deepcopy(R[i])
  T[i][i] = 0
  while S:
    t = S.pop()
    if t[1] <= L:
      if t[1] < T[i][t[0]]:
        T[i][t[0]] = t[1]
        for j in R[t[0]]:
          if t[1] + j[1] <= L:
            S.append([j[0], t[1] + j[1]])

for i in range(N):
  for j in range(N):
    if i == j:
      T[i][j] = 0
      continue
    if T[i][j] <= L:
      T[i][j] = 1
    else:
      T[i][j] = inf

for k in range(N):
  for i in range(N):
    for j in range(N):
      T[i][j] = min(T[i][j], T[i][k] + T[k][j])

for s, t in st:
  s -= 1
  t -= 1
  if T[s][t] == inf:
    print(-1)
  else:
    print(T[s][t] - 1)


Fixed submission:
import sys

N, M, L = list(map(int, input().split()))
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
Q = int(input())
st = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

inf = 10 ** 10
D = [[inf] * N for _ in range(N)]
R = {}

for a, b, c in ABC:
  a -= 1
  b -= 1
  D[a][b] = c
  D[b][a] = c
  if a not in R:
    R[a] = [[b, c]]
  else:
    R[a].append([b, c])
  if b not in R:
    R[b] = [[a, c]]
  else:
    R[b].append([a, c])

for i in range(N):
  D[i][i] = 0

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])


for i in range(N):
  for j in range(N):
    if i == j:
      D[i][j] = 0
      continue
    if D[i][j] <= L:
      D[i][j] = 1
    else:
      D[i][j] = inf

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])

for s, t in st:
  s -= 1
  t -= 1
  if D[s][t] == inf:
    print(-1)
  else:
    print(D[s][t] - 1)
Buggy python submission (verdict: Time Limit Exceeded):
#解説読んだ

import math

N, L = list(map(int, input().split()))
T = [int(input()) for _ in range(N)]

K = N * (N - 1) * (N - 2) / 3 / 2
x, y = 0, 0
for i in range(N - 1):
  for j in range(i + 1, N):
    a = (T[i] + T[j]) / 2
    b = a + L / 2
    t = j - i - 1
    k = N - 2 - t
    x += k * math.cos(2 * math.pi * a / L) / K
    x += t * math.cos(2 * math.pi * b / L) / K
    y += k * math.sin(2 * math.pi * a / L) / K
    y += t * math.sin(2 * math.pi * b / L) / K
print(x, y)

Fixed submission:
#解説読んだ

import math

N, L = list(map(int, input().split()))
T = [int(input()) for _ in range(N)]

K = N * (N - 1) * (N - 2) / 3 / 2
x, y = 0, 0
for i in range(N - 1):
  for j in range(i + 1, N):
    a = (T[i] + T[j]) / 2
    b = a + L / 2
    t = j - i - 1
    k = N - 2 - t
    x += k * math.cos(2 * math.pi * a / L) / K
    x += t * math.cos(2 * math.pi * b / L) / K
    y += k * math.sin(2 * math.pi * a / L) / K
    y += t * math.sin(2 * math.pi * b / L) / K
print(x, y)

Buggy python submission (verdict: Time Limit Exceeded):
#解説読んだ

import math

N, L = list(map(int, input().split()))
T = [int(input()) for _ in range(N)]

x, y = 0, 0
for i in range(N - 1):
  for j in range(i + 1, N):
    a = (T[i] + T[j]) / 2
    b = a + L / 2
    t = j - i - 1
    k = N - 2 - t
    x += k * math.cos(2 * math.pi * a / L)
    x += t * math.cos(2 * math.pi * b / L)
    y += k * math.sin(2 * math.pi * a / L)
    y += t * math.sin(2 * math.pi * b / L)
x /= N * (N - 1) * (N - 2) / 3 / 2
y /= N * (N - 1) * (N - 2) / 3 / 2
print(x, y)

Fixed submission:
#解説読んだ

import math

N, L = list(map(int, input().split()))
T = [int(input()) for _ in range(N)]

K = N * (N - 1) * (N - 2) / 3 / 2
x, y = 0, 0
for i in range(N - 1):
  for j in range(i + 1, N):
    a = (T[i] + T[j]) / 2
    b = a + L / 2
    t = j - i - 1
    k = N - 2 - t
    x += k * math.cos(2 * math.pi * a / L) / K
    x += t * math.cos(2 * math.pi * b / L) / K
    y += k * math.sin(2 * math.pi * a / L) / K
    y += t * math.sin(2 * math.pi * b / L) / K
print(x, y)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = list(map(int, input().split()))
abc = []

for i in range(M):
  t = list(map(int, input().split()))
  k = list(map(int, input().split()))
  x = 0
  for j in k:
    x += (1 << (j - 1))
  abc.append(t + [x])

def nasu(n):
  ans = inf
  for i in range(1, n - 1):
    if ~n & i == 0:
      ans = min(ans, L[i] + L[n ^ i])
  return ans

inf = 10 ** 10
L = [inf] * (1 << N)

for i in range(1, N + 1):
  n = (1 << i) - 1
  while n < (1 << N):
    for j in range(M):
      if ~abc[j][2] & n == 0:
        L[n] = min(L[n], abc[j][0])
    L[n] = min(L[n], nasu(n))
    x = n & -n
    y = n + x
    n = ((n & ~y) // x >> 1) | y

if L[-1] == inf:
  print(-1)
else:
  print(L[-1])



Fixed submission:
N, M = list(map(int, input().split()))
abc = []

for i in range(M):
  t = list(map(int, input().split()))
  k = list(map(int, input().split()))
  x = 0
  for j in k:
    x += (1 << (j - 1))
  abc.append(t + [x])

def nasu(n):
  ans = inf
  for i in range(1, n - 1):
    if ~n & i == 0:
      ans = min(ans, L[i] + L[n ^ i])
  return ans

inf = 10 ** 10
L = [inf] * (1 << N)

for i in range(1, N + 1):
  n = (1 << i) - 1
  while n < (1 << N):
    for j in range(M):
      if ~abc[j][2] & n == 0:
        L[n] = min(L[n], abc[j][0])
    L[n] = min(L[n], nasu(n))
    x = n & -n
    y = n + x
    n = ((n & ~y) // x >> 1) | y

if L[-1] == inf:
  print(-1)
else:
  print(L[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = list(map(int, input().split()))

S.sort(reverse = True)
L = []

cnt = 1
for i in range(1, len(S)):
  if S[i] == S[i - 1]:
    cnt += 1
  else:
    L.append(cnt)
    cnt = 1
L.append(cnt)

if L[0] != 1:
  print("No")
  exit()

DP = [[0] * N for _ in range(len(L))]
S = [0] * len(L)

for i in range(N):
  DP[0][i]= 1

for i in range(1, len(L)):
  for j in range(N):
    DP[i][j] = DP[i - 1][j]
  
  t = L[i]
  k = 0
  P = [0] * N
  for j in range(N):
    P[j] = k
    if DP[i][j] > t:
      DP[i][j] -= t
      k += t
      t = 0
    else:
      t -= DP[i][j]
      k += DP[i][j]
      DP[i][j] = 0
  if t != 0:
    print("No")
    exit()
  for j in range(N):
    DP[i][j] += P[j]

print("Yes")

Fixed submission:
N = int(input())
S = list(map(int, input().split()))

S.sort(reverse = True)
L = []

cnt = 1
for i in range(1, len(S)):
  if S[i] == S[i - 1]:
    cnt += 1
  else:
    L.append(cnt)
    cnt = 1
L.append(cnt)

if L[0] != 1:
  print("No")
  exit()

DP = [[0] * N for _ in range(len(L))]
S = [0] * len(L)

for i in range(N):
  DP[0][i]= 1

for i in range(1, len(L)):
  for j in range(N):
    DP[i][j] = DP[i - 1][j]
  
  t = L[i]
  k = 0
  P = [0] * N
  for j in range(N):
    P[j] = k
    if DP[i][j] > t:
      DP[i][j] -= t
      k += t
      t = 0
    else:
      t -= DP[i][j]
      k += DP[i][j]
      DP[i][j] = 0
  if t != 0:
    print("No")
    exit()
  for j in range(N):
    DP[i][j] += P[j]

print("Yes")