Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N, A, B, C, *L = map(int, open('0').read().split())
ans = float('inf')
for i in range(4**N):
  a = 0
  b = 0
  c = 0
  m = 0
  for j in range(N):
    if i%4==0:
      if a!=0:
        m += 10
      a += L[j]
    elif i%4==1:
      if b!=0:
        m += 10
      b += L[j]
    elif i%4==2:
      if c!=0:
        m += 10
      c += L[j]
    i //= 4
  if a==0 or b==0 or c==0:
    continue
  ans = min(ans, m+abs(A-a)+abs(B-b)+abs(C-c))
print(ans)

Fixed submission:
N, A, B, C = map(int, input().split())
ls = [int(input()) for i in range(N)]

def dfs(cur, a, b, c):
  if cur==N:
    return abs(A-a)+abs(B-b)+abs(C-c)-30 if min(a,b,c)>0 else 10**9
  ret0 = dfs(cur+1, a+ls[cur], b, c)+10
  ret1 = dfs(cur+1, a, b+ls[cur], c)+10
  ret2 = dfs(cur+1, a, b, c+ls[cur])+10
  ret3 = dfs(cur+1, a, b, c)
  return min(ret0, ret1, ret2, ret3)
print(dfs(0,0,0,0))

Buggy python submission (verdict: Runtime Error):
N, A, B, C = map(int, input().split())
ls = [int(input) for i in range(N)]

def dfs(cur, a, b, c):
  if cur==N:
    return abs(A-a)+abs(B-b)+abs(C-c)-30 if min(a,b,c)>0 else 10**9
  ret0 = dfs(cur+1, a+ls[cur], b, c)
  ret1 = dfs(cur+1, a, b+ls[cur], c)
  ret2 = dfs(cur+1, a, b, c+ls[cur])
  ret3 = dfs(cur+1, a, b, c)
  return min(ret0, ret1, ret2, ret3)
print(dfs(0,0,0,0))

Fixed submission:
N, A, B, C = map(int, input().split())
ls = [int(input()) for i in range(N)]

def dfs(cur, a, b, c):
  if cur==N:
    return abs(A-a)+abs(B-b)+abs(C-c)-30 if min(a,b,c)>0 else 10**9
  ret0 = dfs(cur+1, a+ls[cur], b, c)+10
  ret1 = dfs(cur+1, a, b+ls[cur], c)+10
  ret2 = dfs(cur+1, a, b, c+ls[cur])+10
  ret3 = dfs(cur+1, a, b, c)
  return min(ret0, ret1, ret2, ret3)
print(dfs(0,0,0,0))
Buggy python submission (verdict: Runtime Error):
import numpy as np
A, B, Q, *L = map(int, open('0').read().split())
s = L[:A]
t = L[A:A+B]
x = L[A+B:]

s = [-float('inf')]+s+[float('inf')]
t = [-float('inf')]+t+[float('inf')]
sls = np.searchsorted(s,x)
tls = np.searchsorted(t,x)
for ar, br, c in zip(sls,tls,x):
  bl = br-1
  al = ar-1
  n = s[ar]-t[bl]+min(s[ar]-c,c-t[bl])
  m = t[br]-s[al]+min(t[br]-c,c-s[al])
  p = c-min(t[bl],s[al])
  q = max(s[ar],t[br])-c
  print(min(n,m,p,q))

Fixed submission:
from bisect import bisect_left
INF = 10**18
A, B, Q = map(int, input().split())
als = [int(input()) for i in range(A)]
bls = [int(input()) for i in range(B)]
als = [-INF]+als+[INF]
bls = [-INF]+bls+[INF]

for i in range(Q):
  x = int(input())
  ai = bisect_left(als,x)
  bi = bisect_left(bls,x)
  res = INF
  for S in [als[ai], als[ai-1]]:
    for T in [bls[bi], bls[bi-1]]:
      d1, d2 = abs(S-x)+abs(T-S), abs(T-x)+abs(S-T)
      res = min(res,d1,d2)
  print(res)

Buggy python submission (verdict: Runtime Error):
from bisect import bisect_right
INF = 10**18
A, B, Q = map(int, input().split())
als = [int(input()) for i in range(A)]
bls = [int(input()) for i in range(B)]
als = [-INF]+als+[INF]
bls = [-INF]+bls+[INF]

for i in range(Q):
  x = int(input())
  ai = bisect_right(x,als)
  bi = bisect_right(x,bls)
  res = INF
  for S in [als[ai], als[ai-1]]:
    for T in [bls[bi], bls[bi-1]]:
      d1, d2 = abs(S-x)+abs(T-S), abs(T-x)+abs(S-T)
      res = min(res,d1,d2)
  print(res)

Fixed submission:
from bisect import bisect_left
INF = 10**18
A, B, Q = map(int, input().split())
als = [int(input()) for i in range(A)]
bls = [int(input()) for i in range(B)]
als = [-INF]+als+[INF]
bls = [-INF]+bls+[INF]

for i in range(Q):
  x = int(input())
  ai = bisect_left(als,x)
  bi = bisect_left(bls,x)
  res = INF
  for S in [als[ai], als[ai-1]]:
    for T in [bls[bi], bls[bi-1]]:
      d1, d2 = abs(S-x)+abs(T-S), abs(T-x)+abs(S-T)
      res = min(res,d1,d2)
  print(res)

Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left
INF = 10**18
A, B, Q = map(int, input().split())
als = [int(input()) for i in range(A)]
bls = [int(input()) for i in range(B)]
als = [-INF]+als+[INF]
bls = [-INF]+bls+[INF]

for i in range(Q):
  x = int(input())
  ai = bisect_left(x,als)
  bi = bisect_left(x,bls)
  res = INF
  for S in [als[ai], als[ai-1]]:
    for T in [bls[bi], bls[bi-1]]:
      d1, d2 = abs(S-x)+abs(T-S), abs(T-x)+abs(S-T)
      res = min(res,d1,d2)
  print(res)

Fixed submission:
from bisect import bisect_left
INF = 10**18
A, B, Q = map(int, input().split())
als = [int(input()) for i in range(A)]
bls = [int(input()) for i in range(B)]
als = [-INF]+als+[INF]
bls = [-INF]+bls+[INF]

for i in range(Q):
  x = int(input())
  ai = bisect_left(als,x)
  bi = bisect_left(bls,x)
  res = INF
  for S in [als[ai], als[ai-1]]:
    for T in [bls[bi], bls[bi-1]]:
      d1, d2 = abs(S-x)+abs(T-S), abs(T-x)+abs(S-T)
      res = min(res,d1,d2)
  print(res)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
N,M,*A = map(int, open(0).read().split())
ls = [0]*10
ls[1] = 2
ls[2] = 5
ls[3] = 5
ls[4] = 4
ls[5] = 5
ls[6] = 6
ls[7] = 3
ls[8] = 7
ls[9] = 6
dic = defaultdict(int)
for a in A:
  k = ls[a]
  dic[k] = max(dic[k],a)
dp = [-1]*(N+1)
for k in dic.keys():
  if k>N:
    continue
  dp[k] = dic[k]
for i in range(N+1):
  for k in dic.keys():
    if i-k>0 and dp[i-k]!=-1:
      s = str(dp[i-k])
      m = int(s+str(dic[k]))
      dp[i] = max(dp[i], m)
print(dp[N])

Fixed submission:
from fractions import gcd
from functools import reduce

def Gcd(*numbers):
  return reduce(gcd, numbers)
N = int(input())
ls = [int(i) for i in input().split()]

print(Gcd(*ls))
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
a = [int(i) for i in input().split()]
s = bin(K)[1:]
length = len(s)+1
ls = [[0,length-i-1] for i in range(len(s)+1)]

for i in a:
  s = bin(i)[2:]
  while len(s)<length:
    s = '0'+s
  for j in range(len(s)):
    if s[j]=='1':
      ls[j][0] += 1
dic = {}
for i in range(len(ls)):
  x, n = ls[i]
  s = (2**n)*(N-x)-(2**n)*x
  ls[i] = (s,n)
  dic[n]=s
dp = [0]*(length+1)
dp[0] = sum(a)
for i in range(1,length+1):
  if 2**(i-1)>K:
    print(dp[i-1])
    break
  if dic[i-1]>0:
    dp[i] = dp[i-1]+dic[i-1]
  else:
    dp[i] = dp[i-1]
else:
  print(dp[-1])

Fixed submission:
N, K = map(int, input().split())
a = [int(i) for i in input().split()]
m = -1
for i in a:
  if i>m:
    m = i
m = max(K,m)
s = bin(m)[2:]
length = len(s)
ls = [[0,length-i-1] for i in range(length)]

for i in a:
  s = bin(i)[2:]
  while len(s)<length:
    s = '0'+s
  for j in range(length):
    if s[j]=='1':
      ls[j][0] += 1
dic = {}
for i in range(length):
  x, n = ls[i]
  s = (2**n)*(N-x)-(2**n)*x
  dic[n]=s
s = bin(K+1)[2:]
ils = [len(s)-i-1 for i in range(len(s)) if s[i]=='1']
xls = []
for i in range(len(ils)):
  m = ''
  for j in range(ils[i]):
    if dic[j]>0:
      m+='1'
    else:
      m+='0'
  m += '0'
  while len(m)<len(s):
    m += s[len(s)-len(m)-1]
  m = m[::-1]
  xls += [int(m,2)]

ans = 0
for x in xls:
  h = 0
  for u in a:
    h += x^u
  if h>ans:
    ans = h
print(ans)

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
a = [int(i) for i in input().split()]
m = -1
for i in a:
  if i>m:
    m = i
s = bin(m)[1:]
length = len(s)+1
ls = [[0,length-i-1] for i in range(len(s)+1)]

for i in a:
  s = bin(i)[2:]
  while len(s)<length:
    s = '0'+s
  for j in range(len(s)):
    if s[j]=='1':
      ls[j][0] += 1
dic = {}
for i in range(len(ls)):
  x, n = ls[i]
  s = (2**n)*(N-x)-(2**n)*x
  ls[i] = (s,n)
  dic[n]=s
s = bin(K)[1:]
length = len(s)
dp = [0]*(length+1)
dp[0] = sum(a)
for i in range(1,length+1):
  if 2**(i-1)>K:
    print(dp[i-1])
    break
  if dic[i-1]>0:
    dp[i] = dp[i-1]+dic[i-1]
  else:
    dp[i] = dp[i-1]
else:
  print(dp[-1])

Fixed submission:
N, K = map(int, input().split())
a = [int(i) for i in input().split()]
m = -1
for i in a:
  if i>m:
    m = i
m = max(K,m)
s = bin(m)[2:]
length = len(s)
ls = [[0,length-i-1] for i in range(length)]

for i in a:
  s = bin(i)[2:]
  while len(s)<length:
    s = '0'+s
  for j in range(length):
    if s[j]=='1':
      ls[j][0] += 1
dic = {}
for i in range(length):
  x, n = ls[i]
  s = (2**n)*(N-x)-(2**n)*x
  dic[n]=s
s = bin(K+1)[2:]
ils = [len(s)-i-1 for i in range(len(s)) if s[i]=='1']
xls = []
for i in range(len(ils)):
  m = ''
  for j in range(ils[i]):
    if dic[j]>0:
      m+='1'
    else:
      m+='0'
  m += '0'
  while len(m)<len(s):
    m += s[len(s)-len(m)-1]
  m = m[::-1]
  xls += [int(m,2)]

ans = 0
for x in xls:
  h = 0
  for u in a:
    h += x^u
  if h>ans:
    ans = h
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import deque
def main():
  N, M, *L = map(int, open(0).read().split())
  dic = [[] for i in range(N+1)]
  par =  [None]*N
  cnt = [0]*(N+1)
  cnt[0] = 1
  for a,b in zip(*[iter(L)]*2):
    dic[a].append(b)
    cnt[b] += 1

  for i, m in enumerate(cnt):
    if m==0:
      q = deque([i])
      par[i-1] = 0
      break
  
  while q:
    m = q.popleft()
    for c in dic[m]:
      cnt[c] -= 1
      if cnt[c]==0:
        par[c-1] = str(m)
        q.append(c)

  ans = '\n'.join(par)
  print(ans)
  
if __name__== '__main__':
  main()

Fixed submission:
from collections import defaultdict, deque
N, M = map(int, input().split())
dic = defaultdict(list)
par =  [0]*(N+1)
cnt = [0]*(N+1)
for i in range(N-1+M):
  a, b = map(int, input().split())
  dic[a] += [b]
  cnt[b] += 1

for i in range(1,N+1):
  if cnt[i]==0:
    q = deque([i])
    break
  
while q:
  m = q.popleft()
  for c in dic[m]:
    cnt[c] -= 1
    if cnt[c]==0:
      par[c] = m
      q += [c]

for i in range(1,N+1):
  print(par[i])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict, deque
N, M = map(int, input().split())
dic = defaultdict(list)
par =  [0]*(N+1)
dist = [-1]*(N+1)
for i in range(N-1+M):
  a, b = map(int, input().split())
  dic[a] += [b]
  par[b] = a
for i in range(1,N+1):
  if par[i]==0:
    q = deque([(i,0)])
    dist[i] = 0
    break

while q:
  p, cnt = q.popleft()
  if dist[p]>cnt:
    continue
  for e in dic[p]:
    if dist[e]<dist[p]+1:
      dist[e] = dist[p]+1
      q += [(e,dist[e])]
      par[e] = p
for i in range(1,N+1):
  print(par[i])

Fixed submission:
from collections import defaultdict, deque
N, M = map(int, input().split())
dic = defaultdict(list)
par =  [0]*(N+1)
cnt = [0]*(N+1)
for i in range(N-1+M):
  a, b = map(int, input().split())
  dic[a] += [b]
  cnt[b] += 1

for i in range(1,N+1):
  if cnt[i]==0:
    q = deque([i])
    break
  
while q:
  m = q.popleft()
  for c in dic[m]:
    cnt[c] -= 1
    if cnt[c]==0:
      par[c] = m
      q += [c]

for i in range(1,N+1):
  print(par[i])
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
from heapq import heappush, heappop
N,K,*L = map(int, open(0).read().split())
dic = defaultdict(list)
ls = []
for i,(t,d) in enumerate(zip(*[iter(L)]*2)):
  dic[t].append(d)
  heappush(ls,(-d,t))
S = set()
pre = []
ans = 0
num = 0
for i in range(K):
  d,t = heappop(ls)
  ans -= d
  if t not in S:
    num += 1
    S.add(t)
  else:
    heappush(pre,-d)
ans += num*num
m = ans
for i in range(N-K):
  d,t = heappop(ls)
  if t in S:
    continue
  S.add(t)
  m -= heappop(pre)
  m += -d+2*num+1
  num += 1
  ans = max(ans,m)
  if pre==[]:
    break
print(ans)

Fixed submission:
from heapq import heappush, heappop
N, K = map(int, input().split())
log = [0]*N
pre = []
ls = []
for i in range(N):
  t, d = map(int, input().split())
  t = t-1
  heappush(ls,(-d,t))
v = 0
n = 0
for i in range(K):
  d, t = heappop(ls)
  d = -d
  log[t] += 1
  v += d
  if log[t]>1:
    heappush(pre,(d,t))
  else:
    n += 1
v += n*n
ans = v
while ls and pre:
  d, t = heappop(ls)
  if log[t]>0:
    continue
  log[t] += 1
  d = -d
  pv = v
  x, y = heappop(pre)
  v -= x
  v += d
  v += 2*n+1
  n += 1
  if ans<v:
    ans = v
print(ans)

Buggy python submission (verdict: Runtime Error):
from heapq import heappush, heappop
N, K = map(int, input().split())
log = [0]*N
pre = []
ls = []
for i in range(N):
  t, d = map(int, input().split())
  t = t-1
  heappush(ls,(-d,t))
v = 0
n = 0
for i in range(K):
  d, t = heappop(ls)
  d = -d
  log[t] += 1
  v += d
  if log[t]>1:
    heappush(pre,(d,t))
  else:
    n += 1
v += n*n
ans = v
while ls:
  d, t = heappop(ls)
  if log[t]>0:
    continue
  log[t] += 1
  d = -d
  pv = v
  x, y = heappop(pre)
  v -= x
  v += d
  v += 2*n+1
  n += 1
  if ans<v:
    ans = v
print(ans)

Fixed submission:
from heapq import heappush, heappop
N, K = map(int, input().split())
log = [0]*N
pre = []
ls = []
for i in range(N):
  t, d = map(int, input().split())
  t = t-1
  heappush(ls,(-d,t))
v = 0
n = 0
for i in range(K):
  d, t = heappop(ls)
  d = -d
  log[t] += 1
  v += d
  if log[t]>1:
    heappush(pre,(d,t))
  else:
    n += 1
v += n*n
ans = v
while ls and pre:
  d, t = heappop(ls)
  if log[t]>0:
    continue
  log[t] += 1
  d = -d
  pv = v
  x, y = heappop(pre)
  v -= x
  v += d
  v += 2*n+1
  n += 1
  if ans<v:
    ans = v
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left
N,Q,*L = map(int, open(0).read().split())
A = L[:N]
S = []
M = []
x = 0
y = 0
m = sum(A)
for i in range(N):
  if i%2==0:
    x += A[i]
    S.append(x)
  else:
    y += A[i]
    S.append(y)
for i in range(N):
  M.append(m)
  m -= A[i]

for q in L[N:]:
  i = bisect_left(A,q)
  if 0<i<N and q-A[i-1]<=A[i]-q:
    i = i-1
  if i>=N-1:
    print(S[N-1])
    continue
  l = -1
  r = N
  while l+1<r:
    s = (l+r)//2
    k = N-1-s
    if s<=i:
      l = s
      continue
    x = s-i+1
    if x>k:
      r = s
      continue
    y = k-x
    m = i-y-1
    if m<0:
      l = s
      continue
    if q-A[m]<=A[s]-q:
      r = s
    else:
      l = s
  a = M[r]
  cnt = N-r
  cnt -= r-i-1
  b = i-cnt
  if b>=0:
    a += S[b]
  print(a)

Fixed submission:
from bisect import bisect_left
N,Q,*L = map(int, open(0).read().split())
A = L[:N]
S = []
M = []
x = 0
y = 0
m = sum(A)
for i in range(N):
  if i%2==0:
    x += A[i]
    S.append(x)
  else:
    y += A[i]
    S.append(y)
for i in range(N):
  M.append(m)
  m -= A[i]

for q in L[N:]:
  i = bisect_left(A,q)
  if 0<i<N and q-A[i-1]<=A[i]-q:
    i = i-1
  if i>=N-1:
    print(S[N-1])
    continue
  l = -1
  r = N
  while l+1<r:
    s = (l+r)//2
    k = N-1-s
    if s<=i:
      l = s
      continue
    x = s-i+1
    if x>k:
      r = s
      continue
    y = k-x
    m = i-y-1
    if m<0:
      l = s
      continue
    if q-A[m]<=A[s]-q:
      r = s
    else:
      l = s
  a = M[r]
  cnt = N-r
  cnt -= r-i-1
  b = i-cnt
  if b>=0:
    a += S[b]
  print(a)

Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left
N,Q,*L = map(int, open(0).read().split())
A = L[:N]
S = []
M = []
x = 0
y = 0
m = sum(A)
for i in range(N):
  if i%2==0:
    x += A[i]
    S.append(x)
  else:
    y += A[i]
    S.append(y)
for i in range(N):
  M.append(m)
  m -= A[i]

for q in L[N:]:
  i = bisect_left(A,q)
  if 0<i and q-A[i-1]<=A[i]-q:
    i = i-1
  if i>=N-1:
    print(S[N-1])
    continue
  l = -1
  r = N
  while l+1<r:
    s = (l+r)//2
    k = N-1-s
    if s<=i:
      l = s
      continue
    x = s-i+1
    if x>k:
      r = s
      continue
    y = k-x
    m = i-y-1
    if m<0:
      l = s
      continue
    if q-A[m]<=A[s]-q:
      r = s
    else:
      l = s
  a = M[r]
  cnt = N-r
  cnt -= r-i-1
  b = i-cnt
  if b>=0:
    a += S[b]
  print(a)

Fixed submission:
from bisect import bisect_left
N,Q,*L = map(int, open(0).read().split())
A = L[:N]
S = []
M = []
x = 0
y = 0
m = sum(A)
for i in range(N):
  if i%2==0:
    x += A[i]
    S.append(x)
  else:
    y += A[i]
    S.append(y)
for i in range(N):
  M.append(m)
  m -= A[i]

for q in L[N:]:
  i = bisect_left(A,q)
  if 0<i<N and q-A[i-1]<=A[i]-q:
    i = i-1
  if i>=N-1:
    print(S[N-1])
    continue
  l = -1
  r = N
  while l+1<r:
    s = (l+r)//2
    k = N-1-s
    if s<=i:
      l = s
      continue
    x = s-i+1
    if x>k:
      r = s
      continue
    y = k-x
    m = i-y-1
    if m<0:
      l = s
      continue
    if q-A[m]<=A[s]-q:
      r = s
    else:
      l = s
  a = M[r]
  cnt = N-r
  cnt -= r-i-1
  b = i-cnt
  if b>=0:
    a += S[b]
  print(a)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
h = [int(i) for i in input().split()]
INF = 10**9
dp = [0]*N
for i in range(1,N):
  m = INF
  for j in range(1,K+1):
    if i-j<0:
      break
    x = dp[i-j]+abs(h[i]-h[i-j])
    if m>x:
      m = x
  dp[i] = m
print(dp[-1])

Fixed submission:
N, K = map(int, input().split())
h = [int(i) for i in input().split()]
INF = 10**9
dp = [0]*N
for i in range(1,N):
  m = INF
  for j in range(1,K+1):
    if i-j<0:
      break
    x = dp[i-j]+abs(h[i]-h[i-j])
    if m>x:
      m = x
  dp[i] = m
print(dp[-1])
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
N, *A = map(int, open('0').read().split())
ans = 0
A.sort()
dic = defaultdict(list)
for i, a in enumerate(A):
  dic[a] += [i]
for i in range(N-1,-1,-1):
  a = A[i]
  if dic[a]==[]:
    continue
  dic[a].pop()
  k = 1
  while k<=a:
    k *= 2
  n = k-a
  if dic[n]!=[]:
    dic[n].pop()
    ans += 1
print(ans)


Fixed submission:
from collections import defaultdict
N, *A = map(int, open(0).read().split())
ans = 0
A.sort()
dic = defaultdict(list)
for i, a in enumerate(A):
  dic[a] += [i]
for i in range(N-1,-1,-1):
  a = A[i]
  if dic[a]==[]:
    continue
  dic[a].pop()
  k = 1
  while k<=a:
    k *= 2
  n = k-a
  if dic[n]!=[]:
    dic[n].pop()
    ans += 1
print(ans)

Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left
N, *A = map(int, open(0).read().split())
ans = 0
A.sort()
used = [False]*N
for i in range(N-1,-1,-1):
  if used[i]:
    continue
  a = A[i]
  k = 1
  while k<=a:
    k *= 2
  n = k-a
  ind  = bisect_left(A,n)
  while A[ind]==n:
    if not used[ind] and ind!=i:
      break
    ind += 1
  else:
    continue
  ans += 1
  used[ind] = True
  used[i] = True
print(ans)
  
  

Fixed submission:
from collections import defaultdict
N, *A = map(int, open(0).read().split())
ans = 0
A.sort()
dic = defaultdict(list)
for i, a in enumerate(A):
  dic[a] += [i]
for i in range(N-1,-1,-1):
  a = A[i]
  if dic[a]==[]:
    continue
  dic[a].pop()
  k = 1
  while k<=a:
    k *= 2
  n = k-a
  if dic[n]!=[]:
    dic[n].pop()
    ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
 N, X = map(int, input().split())
2
3 a, p = [1], [1]
4 for i in range(N):
5 a.append(a[i] * 2 + 3)
6 p.append(p[i] * 2 + 1)
7
8 def f(N, X): # X <= 0 や X > a_N を許容し解説本文から簡略化
9 if N == 0:
10 return 0 if X <= 0 else 1
11 elif X <= 1 + a[N-1]:
12 return f(N-1, X-1)
13 else:
14 return p[N-1] + 1 + f(N-1, X-2-a[N-1])
15
16 print(f(N, X))


Fixed submission:
N, X = map(int, input().split())
p = 1
t = 1
pdic = {}
tdic = {}
for i in range(N):
  pdic[i] = p
  tdic[i] = t
  p = 2*p+1
  t = 2*t+3
pdic[N] = p
tdic[N] = t
ans = 0
nokori = X
state = N
count = N
while True:
  while tdic[count]+state-count>nokori:
    count -= 1
    if count<0:
      break
  if count<0:
    break
  nokori -= (tdic[count]+state-count)
  state = count
  ans += pdic[count]
  if nokori==0:
    break
  nokori -= 1
  ans += 1
  if nokori==0:
    break
print(ans)
Buggy python submission (verdict: Runtime Error):
INF = 10**9
N, K = map(int, input().split())
s = input().split()
mc = []
pc = []
for i in s:
  c = int(i)
  if c==0:
    K -= 1
  if c<0:
    mc += [-c]
  elif c>0:
    pc += [c]

mc.sort()
pc.sort()
mc += [INF]
pc += [INF]

m = K-1
xi = 0
yi = -1
while m>0:
  if pc[xi+1]>2*mc[yi+1]:
    yi += 1
  else:
    xi += 1
  m -= 1
if yi!=-1:
  c1 = pc[xi] + 2*mc[yi]
else:
  c1 = pc[xi]

m = K-1
xi = -1
yi = 0
while m>0:
  if mc[yi+1]>2*pc[xi+1]:
    xi += 1
  else:
    yi += 1
  m -= 1
if xi!=-1:
  c2 = 2*pc[xi] + mc[yi]
else:
  c2 = mc[yi]

if K==0:
  print(0)
else:
  print(min(c1, c2))

Fixed submission:
INF = 10**9
N, K = map(int, input().split())
s = [int(c) for c in input().split()]

ans = INF
for i in range(N-K+1):
  l = i
  r = l+K-1
  ans = min(ans, abs(s[l])+abs(s[r]-s[l]), abs(s[r])+abs(s[r]-s[l]))

print(ans)
Buggy python submission (verdict: Runtime Error):
N, M, Q = map(int, input().split())
dp = [[0]*N for i in range(N)]
for i in range(M):
  l, r = map(int, input().split())
  dp[r-1][l-1] += 1
for i in range(N):
  for j in range(N, 0, -1):
    dp[i][j-1] += dp[i][j]
for j in range(N):
  for i in range(N-1):
    dp[i+1][j] += dp[i][j]
for i in range(Q):
  p, q = map(int, input().split())
  print(dp[q-1][p-1])

Fixed submission:
N, M, Q = map(int, input().split())
dp = [[0]*N for i in range(N)]
for i in range(M):
  l, r = map(int, input().split())
  dp[r-1][l-1] += 1
for i in range(N):
  for j in range(N-1, 0, -1):
    dp[i][j-1] += dp[i][j]
for j in range(N):
  for i in range(N-1):
    dp[i+1][j] += dp[i][j]
for i in range(Q):
  p, q = map(int, input().split())
  print(dp[q-1][p-1])

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
N, M, Q = map(int, input().split())
dp = np.zeros((N,N), dtype=np.int32)
for i in range(M):
  l, r = map(int, input().split())
  dp[r-1][l-1] += 1
for i in range(N):
  dp[i] = np.flipud(np.cumsum(np.flipud(dp[i])))
for i in range(N-1):
  dp[i+1] += dp[i]
for i in range(Q):
  p, q = map(int, input().split())
  print(dp[q-1][p-1])

Fixed submission:
N, M, Q = map(int, input().split())
dp = [[0]*N for i in range(N)]
for i in range(M):
  l, r = map(int, input().split())
  dp[r-1][l-1] += 1
for i in range(N):
  for j in range(N-1, 0, -1):
    dp[i][j-1] += dp[i][j]
for j in range(N):
  for i in range(N-1):
    dp[i+1][j] += dp[i][j]
for i in range(Q):
  p, q = map(int, input().split())
  print(dp[q-1][p-1])
Buggy python submission (verdict: Runtime Error):
from collections import Counter
from itertools import accumulate
N, M, *A = map(int, open('0').read().split())
B = [b%M for b in accumulate(A)]
C = Counter(B)
ans = C[0]
ans += sum(C[k]*(C[k]-1)//2 for k in C.keys())
print(ans)

Fixed submission:
from collections import defaultdict
N, M = map(int, input().split())
a = [int(c)%M for c in input().split()]
L = [0]
for i in range(N):
  L += [(L[-1]+a[i])%M]
log = defaultdict(int)
log[0] = 1
ans = 0
for i in range(1,N+1):
  x = L[i]%M
  ans += log[x]
  log[x] += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
N,S = open(0).read().split()
N = int(N)
ldic = defaultdict(int)
rdic = defaultdict(int)
L = S[:N]
R = S[N:][::-1]
for i in range(2**N):
  la = ''
  lb = ''
  ra = ''
  rb = ''
  for j in range(N):
    if i%2==1:
      la += L[j]
      ra += R[j]
    else:
      lb += L[j]
      rb += R[j]
    i >>= 1
  ldic[(la,lb)] += 1
  rdic[(ra,rb)] += 1
ans = sum(rdic[k]*ldic[k] for k in ldic.keys())
print(ans)

Fixed submission:
from collections import defaultdict
N = int(input())
S = input()
S = S[:N]+S[2*N-1:N-1:-1]
ldic = defaultdict(int)
rdic = defaultdict(int)
for i in range(2**N):
  lred = ""
  lblue = ""
  rred = ""
  rblue = ""
  for j in range(N):
    if i%2==1:
      lred += S[j]
      rred += S[N+j]
    else:
      lblue += S[j]
      rblue += S[N+j]
    i >>= 1
  ldic[(lred,lblue)] += 1
  rdic[(rred,rblue)] += 1

ans = 0
for k in ldic.keys():
  ans += ldic[k]*rdic[k]
print(ans)