Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))
Adic={}
for i in range(N):
  if A[i] not in Adic:
    Adic[A[i]] = 1
  else:
    Adic[A[i]] += 1
Aset = set(A)
if 1 in Aset: #1がある場合
  if Adic[1] == 1:
    print(1)
  else:
    print(0)
  exit()
ans = 0
for j in range(N):
  Flag = True
  temp = A[j]
  i = 2
  if Adic[temp] >= 2:
    continue
  while i*i <= temp:
    #print(i,temp)
    if temp%i == 0:
      #print(i,temp//i,temp)
      if i in Aset or temp//i in Aset:
        Flag = False
        #print(i,temp//i,"X")
        break
    i += 1
  if not Flag:
    continue
  ans += 1
print(ans)

Fixed submission:
A = list(map(int,input().split()))
s = sum(A)
ans = 15-s
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import copy
N,K = map(int,input().split())
A = list(map(int,input().split()))
#B = copy.copy(A)
#B = [0 for _ in range(N)]
for t in range(K):
  while min(A) >= N:
    ans = [N]*N
    print(*ans)
    exit()
  B = [0 for _ in range(N)]
  for i in range(N):
    MIN = max(0,i-A[i])
    MAX = min(N-1,i+A[i])
    p = MIN
    while p<=MAX:
      B[p] +=1
      p += 1
  A = B
  #print(B)
print(*B)

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

for i in range(K):
  if min(A) == N:
    ans = [N]*N
    print(*ans)
    exit()
  B = [0 for _ in range(N)]
  for j in range(N):
    left = max(0,j-A[j])
    right = min(N-1,j+A[j])
    B[left] += 1
    if right+1 <= N-1:
      B[right+1] -=1
  #print(B)
  for t in range(1,N):
    B[t] += B[t-1]
  A = B
print(*B)
Buggy python submission (verdict: Time Limit Exceeded):
s = str(input())
n = len(s)
ans = ""
for i in range(n):
  if s[i] == "?":
    ans += "D"
  else:
    ans += s[i]

print(ans)

Fixed submission:
s = str(input())
n = len(s)
t= list(s)
ans = ""
for i in range(n):
  if t[i] == "?":
    t[i] = "D"

ans = ''.join(t)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s = str(input())
n = len(s)
for i in range(n):
  if s[i] == "?":
    if i == 0:
      s = "D" + s[i+1:]
    else:
      s = s[:i] + "D" + s[i+1:]
print(s)

Fixed submission:
s = str(input())
n = len(s)
t= list(s)
ans = ""
for i in range(n):
  if t[i] == "?":
    t[i] = "D"

ans = ''.join(t)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
 
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
 
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
 
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
 
    return result
 
N , M , K = map(int,input().split())
 
ans = 0
for t in range(K+1):
    temp = M*pow(M-1,N-t-1,998244353)
    temp = temp*cmb(N-1, t)%998244353
    ans = (ans+temp)%998244353
print(ans)

Fixed submission:
def cmb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fac[n] * finv[r] * finv[n-r] % p

N , M , K = map(int,input().split())
MOD = 998244353

fac = [-1]*(N+1); fac[0] = 1; fac[1] = 1
finv = [-1]*(N+1); finv[0] = 1; finv[1] = 1
inv = [-1]*(N+1); inv[0] = 0; inv[1] = 1
for i in range(2,N+1):
  fac[i] = fac[i-1]*i%MOD
  inv[i] = MOD - inv[MOD%i]*(MOD//i)%MOD
  finv[i] = finv[i-1]*inv[i]%MOD

ans = 0
for t in range(K+1):
    temp = M*pow(M-1,N-t-1,MOD)
    temp = temp*cmb(N-1,t,MOD)
    ans = (ans+temp)%MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

A = list(map(int, input().split()))

ans = 0
for i in range(N):
  for j in range(max(i,A[i]+1),N):
    if j -i  == A[i]+A[j]:
      ans += 1
print(ans)

Fixed submission:
N = int(input())

A = list(map(int, input().split()))

L = {}
R = {}

for i in range(N):
  t = A[i]+i
  if t in L:
    L[t] += 1
  else:
    L[t] = 1
  s = i - A[i]
  if s in R:
    R[s] += 1
  else:
    R[s] = 1  
#print(L,R)
ans = 0
for i in range(N):
  t = A[i]+i
  #ans += R[t]
  if t in R.keys():
    ans += R[t]
    #print(t,R[t])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

A = list(map(int, input().split()))

ans = 0
for i in range(N):
  for j in range(A[i]+1,N):
    if j -i  == A[i]+A[j]:
      ans += 1
print(ans)

Fixed submission:
N = int(input())

A = list(map(int, input().split()))

L = {}
R = {}

for i in range(N):
  t = A[i]+i
  if t in L:
    L[t] += 1
  else:
    L[t] = 1
  s = i - A[i]
  if s in R:
    R[s] += 1
  else:
    R[s] = 1  
#print(L,R)
ans = 0
for i in range(N):
  t = A[i]+i
  #ans += R[t]
  if t in R.keys():
    ans += R[t]
    #print(t,R[t])
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
A = list(map(int,input().split()))

def zenbu(m, B):
    if m == 1:
        return B[0]
    elif m == 2:
        return max(B[0],B[1])
    elif m == 3:
        return max(B[0],B[1],B[2])
    elif m%2 == 0: #偶数の場合
        temp = 0
        for i in range(m//2-1):
            temp += B[i*2]
        return max(temp+ max(B[m-2],B[m-1]), zenbu(m-2, B)+ B[m-1])
    else:#奇数の場合
        temp = 0
        for i in range((m-1)//2):
            temp += B[i*2]
        return max(temp, zenbu(m-2,B)+ B[m-1], zenbu(m-3,B)+ max(B[m-2],B[m-1]))

ans = zenbu(n,A)

print(ans)

Fixed submission:
a = int(input())

b = [int(x) for x in list(str(a))]

ans =0
for i in range(len(b)):
  if b[i] == 7:
    ans = 1
if ans == 0:
  print("No")
else:
  print("Yes")
Buggy python submission (verdict: Time Limit Exceeded):
import math
n = int(input())

ans = 0
for i in range(1,n+1):
  for j in range(1,n+1):
    for k in range(1,n+1):
      ans += math.gcd(math.gcd(i,j),k)
print(ans)

Fixed submission:
import math
n = int(input())

ans = 0
for i in range(1,n+1):
  for j in range(1,n+1):
    temp = math.gcd(i,j)
    for k in range(1,n+1):
      ans += math.gcd(temp,k)
print(ans)
Buggy python submission (verdict: Runtime Error):
import itertools

n, k ,c = map(int, input().split())
s = list(input())

ok = [] #sから働ける日を抽出
for i in range(n):
  if s[i] == "o":
    ok.append(i)

kouho = list(itertools.combinations(ok, k))

sentaku = []
for i in range(len(kouho)):
  for j in range(k-1):
    if j == 0:
      kankaku = kouho[i][j+1] - kouho[i][j]
    else:
      kankaku = min(kankaku, kouho[i][j+1] - kouho[i][j])
  if kankaku >= c+1:
    sentaku.append(kouho[i])

sentaku1 = list(itertools.chain.from_iterable(sentaku))

for x in ok:
  if sentaku1.count(x) == len(sentaku):
    print(x+1)

Fixed submission:
N,K,C = map(int,input().split())
S = str(input())

L = [] #0index
R = []
now = 0
times = 0
while times < K:
  #print(L)
  if S[now] == "o":
    L.append(now)
    now += C
    times += 1
  now += 1

now = N-1
times = 0
while times < K:
  if S[now] == "o":
    R.append(now)
    now -= C
    times +=1
  now -= 1
R.sort()

#print(L,R)
for i in range(K):
  if L[i] == R[i]:
    print(L[i]+1)
Buggy python submission (verdict: Time Limit Exceeded):
N, P = map(int,input().split())
S = str(input())
L = len(S)
ans = 0
dic = {0:1} #一番右端は0なのでこれは常に必要
now = 0
if P == 2 or P == 5:
  kotae = 0
  for i in range(L):
    if int(S[L-1-i])%P == 0:
      kotae += L-i
  print(kotae)
  exit(0)
else:
  for i in range(L):
    now += int(S[L-1-i])*pow(10,i)
    temp = now%P
    if temp not in dic:
      dic[temp] = 1
    else:
      dic[temp] += 1
#print(dic)
ans = 0  
for i in dic.values():
  if i != 1:
    ans += i*(i-1)//2
print(ans)

Fixed submission:
N, P = map(int,input().split())
S = str(input())
L = len(S)
ans = 0
dic = {0:1} #一番右端は0なのでこれは常に必要
now = 0
if P == 2 or P == 5:
  kotae = 0
  for i in range(L):
    if int(S[L-1-i])%P == 0:
      kotae += L-i
  print(kotae)
  exit(0)
else:
  for i in range(L):
    now += int(S[L-1-i])*pow(10,i,P)
    temp = now%P
    if temp not in dic:
      dic[temp] = 1
    else:
      dic[temp] += 1
#print(dic)
ans = 0  
for i in dic.values():
  if i != 1:
    ans += i*(i-1)//2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input()); MOD = pow(10,9)+7
C= list(map(int,input().split()))
C.sort()

#L = [48,20,8,3,1]
L = [1]
for i in range(1,N):
  temp = (i+2)*pow(2,i-1)
  L.append(temp)
  
L.reverse()
ans = 0
for i in range(N):
  ans = (ans + L[i]*pow(2,i)*C[i])%MOD
#ans = ans%MOD
print(ans*pow(2,N,MOD)%MOD)


Fixed submission:
N = int(input()); MOD = pow(10,9)+7
C= list(map(int,input().split()))
C.sort()

#L = [48,20,8,3,1]
L = [1]
for i in range(1,N):
  temp = (i+2)*pow(2,i-1,MOD)
  L.append(temp)
  
L.reverse()
ans = 0
for i in range(N):
  ans = (ans + L[i]*pow(2,i,MOD)*C[i])%MOD
#ans = ans%MOD
print(ans*pow(2,N,MOD)%MOD)
Buggy python submission (verdict: Runtime Error):
N,T,A = map(int,input().split()); INF = float("inf")
T-=1;A-=1 #0index
G = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1 #0index
  G[a].append(b);G[b].append(a)

disT = [INF for _ in range(N)]; disT[T] = 0
disA = [INF for _ in range(N)]; disA[A] = 0

def dfs(v, L):
  for u in G[v]:
    if L[u] != INF:
      continue
    L[u] = L[v]+1
    dfs(u,L)
dfs(T,disT)
dfs(A,disA)
#print(disT)
#print(disA)
ans = 0
for i in range(N):
  if disT[i] < disA[i]:
    ans = max(ans,disA[i]-1)
print(ans)
    

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
N,T,A = map(int,input().split()); INF = float("inf")
T-=1;A-=1 #0index
G = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1 #0index
  G[a].append(b);G[b].append(a)

disT = [INF for _ in range(N)]; disT[T] = 0
disA = [INF for _ in range(N)]; disA[A] = 0

def dfs(v, L):
  for u in G[v]:
    if L[u] != INF:
      continue
    L[u] = L[v]+1
    dfs(u,L)
dfs(T,disT)
dfs(A,disA)
#print(disT)
#print(disA)
ans = 0
for i in range(N):
  if disT[i] < disA[i]:
    ans = max(ans,disA[i]-1)
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())

g = [[] for _ in range(N)]
hen = []
dic = {}
for i in range(N-1):
  #iが辺のID
  a,b = map(int,input().split())
  a -= 1; b -= 1
  g[a].append((b,i))
  g[b].append((a,i))

#これが答え。
ans = [-1 for _ in range(N-1)]

#vという頂点からpという親にcolorという色で繋がっている。
def dfs(v, color, p):
  k = 1 #色の初期値
  for i in range(len(g[v])): #vから繋がっている頂点をtoとして探す
    TO = g[v][i][0]
    ID = g[v][i][1]
    if TO == p: #親は一つでそれ以外は子。親の時だけ無視すればよい。
      continue
    if k == color: #親から繋がっている色と被ったらダメ。
      k += 1
    ans[ID] = k
    k += 1 #ここで足す1をしないとこのfor loopの中の辺で色が被る。
    dfs(TO,ans[ID],v)

dfs(0,0,-1) #根を0として、仮想親の-1から仮想色0で繋がっている。
print(max(ans))
for i in ans:
  print(i)

Fixed submission:
import sys
sys.setrecursionlimit(500000)

N = int(input())

g = [[] for _ in range(N)]
hen = []
dic = {}
for i in range(N-1):
  #iが辺のID
  a,b = map(int,input().split())
  a -= 1; b -= 1
  g[a].append((b,i))
  g[b].append((a,i))

#これが答え。
ans = [-1 for _ in range(N-1)]

#vという頂点からpという親にcolorという色で繋がっている。
def dfs(v, color, p):
  k = 1 #色の初期値
  for i in range(len(g[v])): #vから繋がっている頂点をtoとして探す
    TO = g[v][i][0]
    ID = g[v][i][1]
    if TO == p: #親は一つでそれ以外は子。親の時だけ無視すればよい。
      continue
    if k == color: #親から繋がっている色と被ったらダメ。
      k += 1
    ans[ID] = k
    k += 1 #ここで足す1をしないとこのfor loopの中の辺で色が被る。
    dfs(TO,ans[ID],v)

dfs(0,0,-1) #根を0として、仮想親の-1から仮想色0で繋がっている。
print(max(ans))
for i in ans:
  print(i)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq
N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
A.sort(reverse=True)
F.sort()

if sum(A) <= K:
  print("0")
  exit(0)

L = []
for i in range(N):
  heapq.heappush(L, (-A[i]*F[i],A[i],F[i]))

for i in range(K):
  temp = heapq.heappop(L)
  rep = (-(temp[1]-1)*temp[2], (temp[1]-1), temp[2])
  heapq.heappush(L, rep)
ans = heapq.heappop(L)
print(-1*ans[0])

Fixed submission:
def solve(B,G,x):
  sums = 0
  for i in range(N):
    req = B[i] - x//G[i] 
    sums += max(0,req)
  if sums <= K:
    return True
  else:
    return False

N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
A.sort(reverse=True)
F.sort()

if sum(A) <= K:
  print("0")
  exit(0)

L = []
MAX = 0
for i in range(N):
  temp = A[i]*F[i]
  MAX = max(MAX,temp)
ng = 1
ok = MAX+1
while abs(ng-ok) > 1:
  mid = (ok+ng)//2
  #print(mid,solve(A,F,mid))
  if solve(A,F,mid):
    ok = mid
  else:
    ng = mid
print(ok)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
A.sort(reverse=True)
F.sort()

L = []
for i in range(N):
  heapq.heappush(L, (-A[i]*F[i],A[i],F[i]))

for i in range(K):
  temp = heapq.heappop(L)
  rep = (-(temp[1]-1)*temp[2], (temp[1]-1), temp[2])
  heapq.heappush(L, rep)
ans = heapq.heappop(L)
print(-1*ans[0])


Fixed submission:
def solve(B,G,x):
  sums = 0
  for i in range(N):
    req = B[i] - x//G[i] 
    sums += max(0,req)
  if sums <= K:
    return True
  else:
    return False

N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
A.sort(reverse=True)
F.sort()

if sum(A) <= K:
  print("0")
  exit(0)

L = []
MAX = 0
for i in range(N):
  temp = A[i]*F[i]
  MAX = max(MAX,temp)
ng = 1
ok = MAX+1
while abs(ng-ok) > 1:
  mid = (ok+ng)//2
  #print(mid,solve(A,F,mid))
  if solve(A,F,mid):
    ok = mid
  else:
    ng = mid
print(ok)
Buggy python submission (verdict: Runtime Error):
import sys
N,M,P = map(int,input().split())
N-=1 #頂点番号を0スタートに
INF = float("inf")
edge = []
to = [[] for _ in range(N+1)] #普通に移動できる点
rto = [[] for _ in range(N+1)] #逆に戻れる点
reachablefrom = [False for _ in range(N+1)] #始点0から終点N-1へ行けるかチェック
reachableto = [False for _ in range(N+1)] #終点N-1から始点0へ戻れるかチェック
OK = [False for _ in range(N+1)] #どちらからもいける点を検出。ここ以外の点はどうでもよい。
for i in range(M):
  a,b,c = map(int,input().split())
  a-=1;b-=1 #頂点番号を0スタートに
  c-=P #ここで先に最後に払う分を引いておく。
  c = -c #最短経路にしたいのでコストを負にする。
  edge.append((a,b,c))
  to[a].append(b)
  rto[b].append(a)

def dfs(v):
  if reachablefrom[v]:
    return
  reachablefrom[v] = True
  for u in to[v]:
    dfs(u)

def rdfs(v):
  if reachableto[v]:
    return
  reachableto[v] = True
  for u in rto[v]:
    rdfs(u)
    
dfs(0)
rdfs(N)
for i in range(len(OK)): #len(OK)でもまあ良いか。
  OK[i] = reachablefrom[i]&reachableto[i]
#ここからベルマンフォード法
d = [INF for _ in range(N+1)]
d[0] = 0 #スタートのコストは0
upd = True #サイクルで更新の有無をチェック
step = 0
while upd:
  upd = False
  for i in range(M):
    a,b,c = edge[i]
    if not OK[a] or not OK[b]:
      continue
    new = d[a]+c
    if new < d[b]: #aから来たほうが最短
      upd = True
      d[b] = new
  step += 1
  if step > N:
    print("-1")
    sys.exit()
ans = -d[N] #最後、コストをマイナスで戻す
ans = max(0,ans)
print(ans)

Fixed submission:
import sys
sys.setrecursionlimit(500000) #これがないと再帰の回数オーバーでエラー出る。
N,M,P = map(int,input().split())
N-=1 #頂点番号を0スタートに
INF = float("inf")
edge = []
to = [[] for _ in range(N+1)] #普通に移動できる点
rto = [[] for _ in range(N+1)] #逆に戻れる点
reachablefrom = [False for _ in range(N+1)] #始点0から終点N-1へ行けるかチェック
reachableto = [False for _ in range(N+1)] #終点N-1から始点0へ戻れるかチェック
OK = [False for _ in range(N+1)] #どちらからもいける点を検出。ここ以外の点はどうでもよい。
for i in range(M):
  a,b,c = map(int,input().split())
  a-=1;b-=1 #頂点番号を0スタートに
  c-=P #ここで先に最後に払う分を引いておく。
  c = -c #最短経路にしたいのでコストを負にする。
  edge.append((a,b,c))
  to[a].append(b)
  rto[b].append(a)

def dfs(v):
  if reachablefrom[v]:
    return
  reachablefrom[v] = True
  for u in to[v]:
    dfs(u)

def rdfs(v):
  if reachableto[v]:
    return
  reachableto[v] = True
  for u in rto[v]:
    rdfs(u)
    
dfs(0)
rdfs(N)
for i in range(len(OK)): #len(OK)でもまあ良いか。
  OK[i] = reachablefrom[i]&reachableto[i]
#ここからベルマンフォード法
d = [INF for _ in range(N+1)]
d[0] = 0 #スタートのコストは0
upd = True #サイクルで更新の有無をチェック
step = 0
while upd:
  upd = False
  for i in range(M):
    a,b,c = edge[i]
    if not OK[a] or not OK[b]:
      continue
    new = d[a]+c
    if new < d[b]: #aから来たほうが最短
      upd = True
      d[b] = new
  step += 1
  if step > N+1:
    print("-1")
    sys.exit()
ans = -d[N] #最後、コストをマイナスで戻す
ans = max(0,ans)
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))
if sum(A) ==0: #すべてゼロ
  print("Yes")
  exit()

if N%3 != 0:
  print("No")
else:
  dic = {}
  for x in A:
    if x in dic:
      dic[x] += 1
    else:
      dic[x] = 1
  V = list(dic.values())
  if V[0] == V[1] and V[1] == V[2]:
    K = list(dic.keys())
    if K[0]^K[1] == K[2] and K[1]^K[2] == K[0] and K[2]^K[0] == K[1]:
      print("Yes")
    else:
      print("No")
  else:
    print("No")

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
if sum(A) ==0: #すべてゼロ
  print("Yes")
  exit()

if N%3 != 0:
  print("No")
else:
  dic = {}
  for x in A:
    if x in dic:
      dic[x] += 1
    else:
      dic[x] = 1
  V = list(dic.values())
  if len(V) == 2:
    K = list(dic.keys())
    if K[0] == 0 and dic[K[1]] == dic[0]*2:
      print("Yes")
    elif K[1] == 0 and dic[K[0]] == dic[0]*2:
      print("Yes")
    else:
      print("No")
    exit()  
  if len(V) != 3:
    print("No")
    exit()
  if V[0] == V[1] and V[1] == V[2]:
    K = list(dic.keys())
    if K[0]^K[1] == K[2] and K[1]^K[2] == K[0] and K[2]^K[0] == K[1]:
      print("Yes")
    else:
      print("No")
  else:
    print("No")
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
dic = defaultdict(int) #初期化する関数。

N = int(input())
X = []
for i in range(N):
  x,y = map(int,input().split())
  X.append([x,y])

for i in range(N):
  for j in range(i+1,N):
    p = X[i][0] - X[j][0]
    q = X[i][1] - X[j][1]
    if p <0:
      p = -p;q=-q
    dic[(p,q)] +=1

path = max(dic.values())
ans = N-path
#print(dic)
print(ans)

Fixed submission:
from collections import defaultdict
dic = defaultdict(int) #初期化する関数。

N = int(input())
if N == 1:
  print(1)
  exit()
X = []
for i in range(N):
  x,y = map(int,input().split())
  X.append([x,y])

for i in range(N):
  for j in range(i+1,N):
    p = X[i][0] - X[j][0]
    q = X[i][1] - X[j][1]
    if p <0:
      p = -p;q=-q
    if p == 0 and q < 0:
      q=-q
    dic[(p,q)] +=1

path = max(dic.values())
ans = N-path
#print(dic)
print(ans)
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
A = set([]); MOD = pow(10,9)+7
for i in range(M):
  a = int(input())
  A.add(a-1)
dp = [[0]*2 for _ in range(N)] #dp[i][j] i段目(0index)にj=0最後1段でj=1最後2段できた。
if 0 not in A:
  dp[0][0] = 1
if 1 not in A:
  dp[1][0] = dp[0][0]+dp[0][1]
  dp[1][1] = 1
for i in range(2,N):
  if i in A:
    continue
  dp[i][0] = (dp[i-1][0]+dp[i-1][1])%MOD
  dp[i][1] = (dp[i-2][0]+dp[i-2][1])%MOD
ans = sum(dp[N-1])%MOD
#print(dp)
print(ans)

Fixed submission:
N,M = map(int,input().split())
A = set([]); MOD = pow(10,9)+7
for i in range(M):
  a = int(input())
  A.add(a-1)
dp = [[0]*2 for _ in range(N)] #dp[i][j] i段目(0index)にj=0最後1段でj=1最後2段できた。
if 0 not in A:
  dp[0][0] = 1
if N == 1:
  print(sum(dp[0]))
  exit()
if 1 not in A:
  dp[1][0] = dp[0][0]+dp[0][1]
  dp[1][1] = 1
for i in range(2,N):
  if i in A:
    continue
  dp[i][0] = (dp[i-1][0]+dp[i-1][1])%MOD
  dp[i][1] = (dp[i-2][0]+dp[i-2][1])%MOD
ans = sum(dp[N-1])%MOD
#print(dp)
print(ans)
Buggy python submission (verdict: Runtime Error):
N,K = map(int,input().split())
A = list(map(int,input().split()))
UP = max(A)
UL = UP.bit_length()
KL = K.bit_length()
MAX = max(UL,KL)
INF = float("inf")
#dp[i][j]: 上からi桁目までを決めて、N未満で確定ならj=1、Nと一致しているならばj=0
dp = [[-INF] * 2 for _ in range(MAX+1)] #-INFにしておかないとないケースから来てしまう。
dp[0][0]=0
ZF = True
L = [[0]*2 for _ in range(MAX)]
for i in range(N):
  for j in range(MAX):
    if A[i]>>j&1 == 1:
      L[MAX-1-j][1] += 1
    else:
      L[MAX-1-j][0] += 1

#print(MAX,KL)
#print(L)
for i in range(MAX):
  fac = pow(2,(MAX-1-i))
  if fac > K: #ここのビットは必ず0．つまり1の個数がかけられる。
    dp[i+1][0] = dp[i][0] + fac*L[i][1]
  else:
    if K>>(KL-1-i)&1 == 1:
      kbit = 1
    else:
      kbit = 0
    #print(kbit,i)
    if kbit == 1: #どちらでも良い
      dp[i+1][1] = max(dp[i][1] + fac*max(L[i]), dp[i][0] + fac*L[i][0]) #未満
      dp[i+1][0] = dp[i][0] + fac*L[i][0] #一致, kbitが1なので0の個数
    else: #完全一致なら0のみ、それ以外ならどちらも
      dp[i+1][1] = max(dp[i][1] + fac*max(L[i]), dp[i][0] + fac*L[i][1]) #未満
      dp[i+1][0] = dp[i][0] + fac*L[i][1] #一致 kbitが0なので1の個数      
#print(dp)
ans = max(dp[MAX])
print(ans)
  


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

A = list(map(int,input().split()))
MAX = max(max(A),K)
l = len(str(bin(MAX)))-2

AB = []
for i in range(N):
  s = str(bin(A[i]))
  temp = s[2:]
  lendif = l - len(temp)
  while lendif > 0:
    temp = "0"+temp
    lendif -= 1
  AB.append(temp)
#print(AB,l)

ans = 0
now = 0 #Kを超えていないかチェックする用。
for i in range(l): #桁数で回す。l-i桁から順にみていく。
  #cは0の数。dは1の数。
  c = 0; d = 0
  for j in range(N):
    if AB[j][i] == "0":
      c += 1
    else:
      d += 1
  if c > d: #0の方が多いので1にしたい。l-i桁目が1の時はKを超えてないか確認。
    if pow(2,l-1-i)+now > K:
      m = d
    else:
      now += pow(2,l-1-i)
      m = c
  else:
    m = d
  #print(m, now, pow(2,l-1-i))
  ans += pow(2,l-1-i)*m
print(ans)
Buggy python submission (verdict: Runtime Error):
import heapq
N,K = map(int,input().split())

L = [[] for _ in range(N)]
All = []
s = set([])
for i in range(N):
  t,d = map(int,input().split())
  t-=1 #0スタートに
  heapq.heappush(L[t], -d) #最大から取り出したいので負にする。
  heapq.heappush(All,[-d,t]) #すべてから大きい順に取り出せるように 
  s.add(t)

#print(L,s)
point = 0
ns = 0 #現在の種類
later = []
now = []
syurui = set([])
while len(now) < K and All:
  temp = heapq.heappop(All)
  if temp[1] not in syurui:
    ns += 1
    point -= temp[0]
    syurui.add(temp[1])
    heapq.heappush(now, -1*temp[0])
  else:
    later.append(temp)
for i in later:
  heapq.heappush(All,i)

point += ns*ns
while len(now) < K:
  temp = heapq.heappop(All)
  point -= temp[0]
  heapq.heappush(now, -1*temp[0])

#print(ns,point)
#print(now,All)
while now[0] < -1*All[0][0]:
  temp = heapq.heappop(All)
  dele = heapq.heappop(now)
  #print(temp,dele)
  upoint = point - temp[0] - dele - ns*ns + (ns-1)**2
  #print(upoint,point)
  if upoint >= point:
    point = upoint
    ns -= 1
  else:
    break
    
print(point)
#print(All)
#print(now)
  

Fixed submission:
import heapq
N,K = map(int,input().split())

L = [[] for _ in range(N)]
All = []
s = set([])
for i in range(N):
  t,d = map(int,input().split())
  t-=1 #0スタートに
  heapq.heappush(L[t], -d) #最大から取り出したいので負にする。
  heapq.heappush(All,[-d,t]) #すべてから大きい順に取り出せるように 
  s.add(t)

#print(L,s)
point = 0
ns = 0 #現在の種類
later = []
now = []
syurui = set([])
while len(now) < K and All:
  temp = heapq.heappop(All)
  if temp[1] not in syurui:
    ns += 1
    point -= temp[0]
    syurui.add(temp[1])
    heapq.heappush(now, -1*temp[0])
  else:
    later.append(temp)
for i in later:
  heapq.heappush(All,i)

point += ns*ns
while len(now) < K:
  temp = heapq.heappop(All)
  point -= temp[0]
  heapq.heappush(now, -1*temp[0])

#print(ns,point)
#print(now,All,All[0][0])
while All and now[0] < -1*All[0][0]:
  temp = heapq.heappop(All)
  dele = heapq.heappop(now)
  #print(temp,dele)
  upoint = point - temp[0] - dele - ns*ns + (ns-1)**2
  #print(upoint,point)
  if upoint >= point:
    point = upoint
    ns -= 1
  else:
    break
    
print(point)
#print(All)
#print(now)