Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
a0=[ai for ai in a]
b=[-1]*(n+1)
base=0
for i in range(n):
    j=n-1-i
    if b[a[j]]==-1:
        c=a.count(a[j])
        b[a[j]]=c
        base+=c*(c-1)//2
        a.pop()
for i in range(n):
    d=b[a0[i]]
    print(base-d+1)


Fixed submission:
n=int(input())
a=list(map(int,input().split()))
a0=[ai for ai in a]
a0.sort()
b=[-1]*(n+1)
base=0
i=0
while i < n:
    t=a0[i]
    c=1
    while i < n-1 and a0[i]==a0[i+1]:
        c+=1
        i+=1
    b[t]=c
    base+=c*(c-1)//2
    i+=1
for i in range(n):
    d=b[a[i]]
    print(base-d+1)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
b=[-1]*(n+1)
base=0
for i in range(n):
    if b[a[i]]==-1:
        c=a.count(a[i])
        b[a[i]]=c
        base+=c*(c-1)//2
for i in range(n):
    d=b[a[i]]
    print(base-d+1)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
a0=[ai for ai in a]
a0.sort()
b=[-1]*(n+1)
base=0
i=0
while i < n:
    t=a0[i]
    c=1
    while i < n-1 and a0[i]==a0[i+1]:
        c+=1
        i+=1
    b[t]=c
    base+=c*(c-1)//2
    i+=1
for i in range(n):
    d=b[a[i]]
    print(base-d+1)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
h,w,k=map(int,input().split())
s=np.array([list(map(int,list(input()))) for _ in range(h)])
def func(catyoko):
  cattate=0
  past=np.array([0]*10)
  now=np.array([0]*10)
  for wi in range(w):
    for i in range(1,len(catyoko)):
      now[i-1]=sum(s[catyoko[i-1]:catyoko[i],wi])
    if max(past+now)>k:
      if max(now)>k:
        return -10
      else:
        cattate+=1
      past=now.copy()
    else:
      past+=now
  return cattate+len(catyoko)-2

# 横方向の割り方は2^(h-1)通りある。h<=10なので横方向の割り方は全探索する。
# 縦方向の割り方は貪欲法
ans=h+w
for i in range(2**(h-1)):
  catyoko=[0]
  for j in range(h-1):
    if ((i>>j) & 1):#立っているビットのところで処理が走る
      catyoko.append(j+1)
  catyoko.append(h)
  a=func(catyoko)
  #print(a,catyoko)
  if a>=0:
    ans=min(ans,a)
print(ans)


Fixed submission:
h,w,k=map(int,input().split())
s=[list(map(int,list(input()))) for _ in range(h)]
def func(catyoko):
  cattate=0
  past=[0]*10
  for wi in range(w):
    now=[0]*10
    for i in range(1,len(catyoko)):
      for j in range(catyoko[i-1],catyoko[i]):
        now[i-1]+=s[j][wi]
    if max([past[i]+now[i] for i in range(10)])>k:
      if max(now)>k:
        return -10
      else:
        cattate+=1
      past=[nowi for nowi in now]
    else:
      for i in range(10):
        past[i]+=now[i]
  return cattate+len(catyoko)-2

# 横方向の割り方は2^(h-1)通りある。h<=10なので横方向の割り方は全探索する。
# 縦方向の割り方は貪欲法
ans=h+w
for i in range(2**(h-1)):
  catyoko=[0]
  for j in range(h-1):
    if ((i>>j) & 1):#立っているビットのところで処理が走る
      catyoko.append(j+1)
  catyoko.append(h)
  a=func(catyoko)
  #print(a,catyoko)
  if a>=0:
    ans=min(ans,a)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
f=np.zeros(9000001,int)
#f[0]=1
#f[a[0]]=1
ans=0
for ai in a:
  ff=np.zeros(9000001,int)
  ff+=f
  ff[ai:]+=f[:-ai]
  ff[0]+=1
  ff[ai]+=1
  f=ff
  f%=mod
  ans+=f[s]
  ans%=mod
print(ans)



Fixed submission:
import numpy as np
n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
f=np.zeros(3001,int)

ans=0
for ai in a:
  ff=np.zeros(3001,int)
  ff+=f
  ff[ai:]+=f[:-ai]
  ff[0]+=1
  ff[ai]+=1
  f=ff
  f%=mod
  ans+=f[s]
  ans%=mod
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
ans=0
for l in range(n):
  dp=[[1]+[0]*3000 for _ in range(n+1)]
  for i in range(l,n):
    for j in range(3001):
        dp[i+1][j]=dp[i][j]
        if j-a[i]>=0:
            dp[i+1][j]+=dp[i][j-a[i]]
        dp[i+1][j]%=mod
    #print(dp[i+1][:10])
    ans+=dp[i+1][s]
    ans%=mod
print(ans)

Fixed submission:
import numpy as np
n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
f=np.zeros(3001,int)

ans=0
for ai in a:
  ff=np.zeros(3001,int)
  ff+=f
  ff[ai:]+=f[:-ai]
  ff[0]+=1
  ff[ai]+=1
  f=ff
  f%=mod
  ans+=f[s]
  ans%=mod
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
ans=0
dp=np.zeros((n+1,3001),np.int64)
for l in range(n):
  dp=np.zeros((n+1,3001),np.int64)
  dp[:,0]=1
  for i in range(l,n):
    dp[i+1]=dp[i]
    dp[i+1,a[i]:]+=dp[i,:-a[i]]
    dp[i+1:]%=mod
    ans+=dp[i+1,s]
    ans%=mod
print(ans)

Fixed submission:
import numpy as np
n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
f=np.zeros(3001,int)

ans=0
for ai in a:
  ff=np.zeros(3001,int)
  ff+=f
  ff[ai:]+=f[:-ai]
  ff[0]+=1
  ff[ai]+=1
  f=ff
  f%=mod
  ans+=f[s]
  ans%=mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):

n=int(input())
a=list(map(lambda x:int(x)-1,list(input())))
def slv(n,a):
    v=a[0]
    if all(v==x for x in a):return 0
    # 答えの偶奇を求める
    chk=0
    tmp=1
    tmpmod=1
    for i in range(n):
        x=a[i]%2
        chk+=a[i]*tmp
        chk%=2
        tmp*=n-1-i
        tmp//=i+1
    if chk:return 1
    if 1 in a:return 0
    a=[x//2 for x in a]
    return slv(n,a)*2

#n=pow(10,5)
#a=[i%3 for i in range(n)]
print(slv(n,a))

Fixed submission:

n=int(input())
a=list(map(lambda x:int(x)-1,list(input())))
memo=[-1]*(n+1)
def log(x):
    if memo[x]!=-1:return memo[x]
    ret=0
    xx=x
    while x and x%2==0:
        x//=2
        ret+=1
    memo[xx]=ret
    return ret

def slv(n,a):
    v=a[0]
    if all(v==x for x in a):return 0
    # 答えの偶奇を求める
    chk=0
    tmppl=0
    tmpmi=0
    for i in range(n):
        x=a[i]%2
        if tmppl>tmpmi:
            pass
        else:
            chk+=a[i]
            chk%=2
        tmppl+=log(n-i-1)
        tmpmi+=log(i+1)
    if chk:return 1
    if 1 in a:return 0
    a=[x//2 for x in a]
    return slv(n,a)*2
print(slv(n,a))
Buggy python submission (verdict: Runtime Error):
n=int(input())
ki=[[] for _ in range(n)]

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

odd=[-1]*n
odd[0]=0
todo=[0]
while todo:
    v=todo.pop()
    for nv in ki[v]:
        if odd[nv]==-1:
            odd[nv]=abs(odd[v]-1)
            todo.append(nv)
from collections import Counter
co=Counter(odd)
ans=[0]*n
if co[1]<n//3:
    cnt1=1
    cnt=2
    cnt3=1
    for i in range(n):
        if odd[i]==1 and 3*cnt3<=n:
            ans[i]=3*cnt3
            cnt3+=1
        else:
            if cnt1%3==0:cnt1+=1
            if cnt1<=n:
                ans[i]=cnt1
                cnt1+=1
            else:
                ans[i]=n-n%3-cnt2*3
                cnt2+=1

elif co[0]<n//3:
    cnt1=1
    cnt2=0
    cnt3=1
    for i in range(n):
        if odd[i]==0 and 3*cnt3<=n:
            ans[i]=3*cnt3
            cnt3+=1
        else:
            if cnt1%3==0:cnt1+=1
            if cnt1<=n:
                ans[i]=cnt1
                cnt1+=1
            else:
                ans[i]=n-n%3-cnt2*3
                cnt2+=1
else:
    cnt1=1
    cnt2=1
    cnt3=1
    for i in range(n):
        if odd[i]==0:
            if 3*cnt1-2<=n:
                ans[i]=3*cnt1-2
                cnt1+=1
            else:
                ans[i]=3*cnt3
                cnt3+=1
        else:
            if 3*cnt2-1<=n:
                ans[i]=3*cnt2-1
                cnt2+=1
            else:
                ans[i]=3*cnt3
                cnt3+=1
print(*ans,sep=' ')



Fixed submission:
n=int(input())
ki=[[] for _ in range(n)]

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

odd=[-1]*n
odd[0]=0
todo=[0]
while todo:
    v=todo.pop()
    for nv in ki[v]:
        if odd[nv]==-1:
            odd[nv]=abs(odd[v]-1)
            todo.append(nv)
from collections import Counter
co=Counter(odd)
ans=[0]*n
if co[1]<=n//3:
    cnt1=1
    cnt2=0
    cnt3=1
    for i in range(n):
        if odd[i]==1 and 3*cnt3<=n:
            ans[i]=3*cnt3
            cnt3+=1
        else:
            if cnt1%3==0:cnt1+=1
            if cnt1<=n:
                ans[i]=cnt1
                cnt1+=1
            else:
                ans[i]=n-n%3-cnt2*3
                cnt2+=1

elif co[0]<=n//3:
    cnt1=1
    cnt2=0
    cnt3=1
    for i in range(n):
        if odd[i]==0 and 3*cnt3<=n:
            ans[i]=3*cnt3
            cnt3+=1
        else:
            if cnt1%3==0:cnt1+=1
            if cnt1<=n:
                ans[i]=cnt1
                cnt1+=1
            else:
                ans[i]=n-n%3-cnt2*3
                cnt2+=1
else:
    cnt1=1
    cnt2=1
    cnt3=1
    for i in range(n):
        if odd[i]==1:
            if 3*cnt1-2<=n:
                ans[i]=3*cnt1-2
                cnt1+=1
            else:
                ans[i]=3*cnt3
                cnt3+=1
        else:
            if 3*cnt2-1<=n:
                ans[i]=3*cnt2-1
                cnt2+=1
            else:
                ans[i]=3*cnt3
                cnt3+=1
print(*ans,sep=' ')
Buggy python submission (verdict: Time Limit Exceeded):
s='0'
s+=input()
n=len(s)
inf=float('inf')
dp=[[inf]*2 for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
  for j in range(2):
    si=int(s[-i-1])
    si+=j
    for a in range(10):
      ni=i+1
      nj=0
      b=a-si
      if b<0:
        nj=1
        b+=10
      dp[ni][nj]=min(dp[ni][nj],dp[i][j]+a+b)
print(dp[n][0])

Fixed submission:
s='0'
s+=input()
n=len(s)
inf=float('inf')
dp=[[inf]*2 for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
  for j in range(2):
    si=int(s[-i-1])
    si+=j
    for a in range(10):
      ni=i+1
      nj=0
      b=a-si
      if b<0:
        nj=1
        b+=10
      dp[ni][nj]=min(dp[ni][nj],dp[i][j]+a+b)
print(dp[n][0])
Buggy python submission (verdict: Runtime Error):
r1,c1,r2,c2=map(int,input().split())
mod=pow(10,9)+7

# コンビネーション、さらに高速。あらかじめO(N)の計算をすることでのちの計算が早くなる
def cmb(n,r,mod):
  if (r<0 or r>n):
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
g1=[1,1] # g1[i]=i! % mod　:階乗
g2=[1,1] # g2[i]=(i!)^(-1) % mod　:階乗の逆元
inverse=[0,1]
n=max(r1,c1,r2,c2)
for i in range(2,2*10**6+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)
ans=0
for k in range(r1,r2+1):
  tmp=cmb(k+1+c2,c2,mod)-cmb(k+1+c1-1,c1-1,mod)
  ans+=tmp
  ans%=mod
print(ans)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)

def main():
  r1,c1,r2,c2=map(int,input().split())
  mod=pow(10,9)+7

  # コンビネーション、さらに高速。あらかじめO(N)の計算をすることでのちの計算が早くなる
  def cmb(n, r, mod):
      if ( r<0 or r>n ):
          return 0
      r = min(r, n-r)
      return g1[n] * g2[r] * g2[n-r] % mod
  g1 = [1, 1] 
  g2 = [1, 1] 
  inverse = [0, 1]
  for i in range( 2, r2+c2+3):
      g1.append( ( g1[-1] * i ) % mod )
      inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
      g2.append( (g2[-1] * inverse[-1]) % mod )
  ans=0
  for r in range(r1,r2+1):
    ans+=cmb(r+c2+1,r+1,mod)-cmb(r+c1,r+1,mod)
    ans%=mod
  print(ans)

if __name__=='__main__':
  main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)

def main():
  r1,c1,r2,c2=map(int,input().split())
  mod=pow(10,9)+7

  # コンビネーション、さらに高速。あらかじめO(N)の計算をすることでのちの計算が早くなる
  def cmb(n, r, mod):
      if ( r<0 or r>n ):
          return 0
      r = min(r, n-r)
      return g1[n] * g2[r] * g2[n-r] % mod
  g1 = [1, 1] 
  g2 = [1, 1] 
  inverse = [0, 1]
  for i in range( 2, r2+c2+1):
      g1.append( ( g1[-1] * i ) % mod )
      inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
      g2.append( (g2[-1] * inverse[-1]) % mod )
  ans=0
  for r in range(r1,r2+1):
    for c in range(c1,c2+1):
      ans+=cmb(r+c,r,mod)
      ans%=mod
  print(ans)

if __name__=='__main__':
  main()


Fixed submission:
import sys
sys.setrecursionlimit(10**7)

def main():
  r1,c1,r2,c2=map(int,input().split())
  mod=pow(10,9)+7

  # コンビネーション、さらに高速。あらかじめO(N)の計算をすることでのちの計算が早くなる
  def cmb(n, r, mod):
      if ( r<0 or r>n ):
          return 0
      r = min(r, n-r)
      return g1[n] * g2[r] * g2[n-r] % mod
  g1 = [1, 1] 
  g2 = [1, 1] 
  inverse = [0, 1]
  for i in range( 2, r2+c2+3):
      g1.append( ( g1[-1] * i ) % mod )
      inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
      g2.append( (g2[-1] * inverse[-1]) % mod )
  ans=0
  for r in range(r1,r2+1):
    ans+=cmb(r+c2+1,r+1,mod)-cmb(r+c1,r+1,mod)
    ans%=mod
  print(ans)

if __name__=='__main__':
  main()
Buggy python submission (verdict: Time Limit Exceeded):
h,n=map(int,input().split())
ab=[list(map(int,input().split()))for _ in range(n)]
maxa=max([a for a,b in ab])
maxmp=pow(10,8)
dp=[maxmp]*(h+maxa) # dp[i]:ダメージをぴったりi与えるのに必要な最小魔力
dp[0]=0
for i in range(h+maxa):
  b=[dp[i-a]+b for a,b in ab if i-a>=0]
  dp[i]=min(dp[i],min(b)) if b else dp[i]
print(min(dp[h:]))

Fixed submission:
import numpy as np
h,n=map(int,input().split())
ab=np.array([list(map(int,input().split())) for _ in range(n)])
dp=np.zeros(10**4+1,np.int64) #dp[i]:残り体力がiのとき、倒すまでの最小魔力
dp[0]=0
for a,b in ab:
      dp[1:a+1]=np.minimum(dp[1:a+1],b)
# a:減らせる体力
# b:魔力
for i in range(1,h+1):
  dp[i]=np.min(dp[i-ab[:,0]]+ab[:,1])
print(dp[h])

Buggy python submission (verdict: Runtime Error):
import numpy as np
h,n=map(int,input().split())
ab=np.array([list(map(int,input().split())) for _ in range(n)])
dp=np.zeros(h+1,np.int64) #dp[i]:残り体力がiのとき、倒すまでの最小魔力
dp[0]=0
for a,b in ab:
      dp[1:a+1]=np.minimum(dp[1:a+1],b)
# a:減らせる体力
# b:魔力
for i in range(1,h+1):
  dp[i]=np.min(dp[i-ab[:,0]]+ab[:,1])
print(dp[-1])


Fixed submission:
import numpy as np
h,n=map(int,input().split())
ab=np.array([list(map(int,input().split())) for _ in range(n)])
dp=np.zeros(10**4+1,np.int64) #dp[i]:残り体力がiのとき、倒すまでの最小魔力
dp[0]=0
for a,b in ab:
      dp[1:a+1]=np.minimum(dp[1:a+1],b)
# a:減らせる体力
# b:魔力
for i in range(1,h+1):
  dp[i]=np.min(dp[i-ab[:,0]]+ab[:,1])
print(dp[h])
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
ans=0
def c(i,j):
  ret=0
  for k in range(1,n+1):
    if str(k)[0]==str(i) and str(k)[-1]==str(j):
      ret+=1
  return ret
for i in range(1,10):
  for j in range(1,10):
    ans+=c(i,j)*c(j,i)
print(ans)

Fixed submission:
def main(n):
  def c(i,j):
    ret=0
    for k in range(1,n+1):
      if str(k)[0]==str(i) and str(k)[-1]==str(j):
        ret+=1
    return ret
  ans=0
  for a in range(1,10):
    for b in range(a,10):
      d=c(a,b)*c(b,a)
      ans+=d
      if a!=b:
        ans+=d
  print(ans)
if __name__=='__main__':
  n=int(input())
  main(n)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
ans=0
def c(i,j):
  ret=0
  for k in range(1,n+1):
    if str(k)[0]==str(i) and str(k)[-1]==str(j):
      ret+=1
  return ret
for i in range(1,10):
  for j in range(1,10):
    ans+=c(i,j)*c(j,i)
print(ans)

Fixed submission:
def main(n):
  def c(i,j):
    ret=0
    for k in range(1,n+1):
      if str(k)[0]==str(i) and str(k)[-1]==str(j):
        ret+=1
    return ret
  ans=0
  for a in range(1,10):
    for b in range(a,10):
      d=c(a,b)*c(b,a)
      ans+=d
      if a!=b:
        ans+=d
  print(ans)
if __name__=='__main__':
  n=int(input())
  main(n)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from collections import deque
h,w=map(int,input().split())
s=[input()for _ in range(h)]
a=np.full((h,w),400,np.int64)
ans=0
def bfs(b,i,j,s):
    b[i,j]=0
    seen=np.zeros((h,w),np.int64)
    todo=deque([(i,j)])
    while np.sum(seen)<h*w and len(todo)>0:
        x,y=todo.popleft()
        if seen[x,y]==1:
            continue
        seen[x,y]=1
        if x>0 and seen[x-1,y]==0 and s[x-1][y]=='.':
            b[x-1,y]=b[x,y]+1
            todo.append((x-1,y))
        if x>0 and s[x-1][y]=='#':
            seen[x-1,y]=1
        if x<h-1 and seen[x+1,y]==0 and s[x+1][y]=='.':
            b[x+1,y]=b[x,y]+1
            todo.append((x+1,y))
        if x<h-1 and s[x+1][y]=='#':
            seen[x+1,y]=1
        if y>0 and seen[x,y-1]==0 and s[x][y-1]=='.':
            b[x,y-1]=b[x,y]+1
            todo.append((x,y-1))
        if y>0 and s[x][y-1]=='#':
            seen[x,y-1]=1
        if y<w-1 and seen[x,y+1]==0 and s[x][y+1]=='.':
            b[x,y+1]=b[x,y]+1
            todo.append((x,y+1))
        if y<w-1 and s[x][y+1]=='#':
            seen[x,y+1]=1
    return np.max(b[b<400])

for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            b=a
            ans=max(ans,bfs(b,i,j,s))
print(ans)


Fixed submission:
from collections import deque
h,w=map(int,input().split())
s=[input()for _ in range(h)]
a=[[400]*w for _ in range(h)]
ans=0
def bfs(b,i,j):
    b[i][j]=0
    seen=[[0]*w for _ in range(h)]
    todo=deque([(i,j)])
    while len(todo)>0:
        x,y=todo.popleft()
        if seen[x][y]==1:
            continue
        seen[x][y]=1
        if x>0 and seen[x-1][y]==0 and s[x-1][y]=='.':
            b[x-1][y]=b[x][y]+1
            todo.append((x-1,y))
        if x>0 and s[x-1][y]=='#':
            seen[x-1][y]=1
        if x<h-1 and seen[x+1][y]==0 and s[x+1][y]=='.':
            b[x+1][y]=b[x][y]+1
            todo.append((x+1,y))
        if x<h-1 and s[x+1][y]=='#':
            seen[x+1][y]=1
        if y>0 and seen[x][y-1]==0 and s[x][y-1]=='.':
            b[x][y-1]=b[x][y]+1
            todo.append((x,y-1))
        if y>0 and s[x][y-1]=='#':
            seen[x][y-1]=1
        if y<w-1 and seen[x][y+1]==0 and s[x][y+1]=='.':
            b[x][y+1]=b[x][y]+1
            todo.append((x,y+1))
        if y<w-1 and s[x][y+1]=='#':
            seen[x][y+1]=1
    ret=0 
    for bi in b:
        for bij in bi:
            if bij<400:
                ret=max(ret,bij)
    #print(b)
    return ret

for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            b=a
            ans=max(ans,bfs(b,i,j))
print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
sgm=pow(10.-7)
def func(c):
    allp=[]
    for i in range(n-1):
        for j in range(i+1,n):
            xi,yi=xy[i]
            xj,yj=xy[j]
            dx=xi-xj
            dy=yi-yj
            d=((xi-xj)**2+(yi-yj)**2)**0.5
            if c**2-(d/2)**2<0:return False
            h=(c**2-(d/2)**2)**0.5
            mx,my=(xi+xj)/2,(yi+yj)/2
            if dx==0:
                allp.append([mx-h,my])
                allp.append([mx+h,my])
            elif dy==0:
                allp.append([mx,my-h])
                allp.append([mx,my+h])
            else:
                dx,dy=dy,-dx
                dh=(dy**2+dx**2)**0.5
                dx*=h/dh
                dy*=h/dh
                allp.append([mx+dx,my+dy])
                allp.append([mx-dx,my-dy])
    for px,py in allp:
        flg=True
        for x,y in xy:
            if ((px-x)**2+(py-y)**2)**0.5>c+sgm:
                flg=False
                break
        if flg:
            return True
    return False

r=2*max([abs(x) for x,y in xy])+max([abs(y) for x,y in xy])
l,r=0,r
for i in range(300):
    c=(l+r)/2
    if func(c):
        l,r=l,c
    else:
        l,r=c,r
print(c)
#print(c**2)

Fixed submission:
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
sgm=pow(10,-7)
def func(c):
    allp=[]
    for i in range(n-1):
        for j in range(i+1,n):
            xi,yi=xy[i]
            xj,yj=xy[j]
            dx=xi-xj
            dy=yi-yj
            d=((xi-xj)**2+(yi-yj)**2)**0.5
            if c**2-(d/2)**2<0:return False
            h=(c**2-(d/2)**2)**0.5
            mx,my=(xi+xj)/2,(yi+yj)/2
            if dx==0:
                allp.append([mx-h,my])
                allp.append([mx+h,my])
            elif dy==0:
                allp.append([mx,my-h])
                allp.append([mx,my+h])
            else:
                dx,dy=dy,-dx
                dh=(dy**2+dx**2)**0.5
                dx*=h/dh
                dy*=h/dh
                allp.append([mx+dx,my+dy])
                allp.append([mx-dx,my-dy])
    for px,py in allp:
        flg=True
        for x,y in xy:
            if ((px-x)**2+(py-y)**2)**0.5>c+sgm:
                flg=False
                break
        if flg:
            return True
    return False

r=2*max([abs(x) for x,y in xy])+max([abs(y) for x,y in xy])
l,r=0,r
for i in range(400):
    c=(l+r)/2
    if func(c):
        l,r=l,c
    else:
        l,r=c,r
print(c)
#print(c**2)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=list(map(int,input().split()))
def factorization(n):
    arr={}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i]=cnt
    if temp!=1:
        arr[temp]=1
    if arr==[]:
        arr[n]=1
    return arr
b=factorization(a[0])[2]
for i in range(1,n):
  if b==factorization(a[i])[2]:
    continue
  else:
    print(0)
    exit(0)
from fractions import gcd
lcmn=a[0]//2
for i in range(1,n):
    lcmn=(lcmn*a[i]//2)//gcd(lcmn,a[i]//2)
print((1+m//lcmn)//2)


Fixed submission:
n,m=map(int,input().split())
a=list(map(int,input().split()))
def func(n):
  ret=0
  n=n/2
  while n.is_integer():
    ret+=1
    n=n/2
  return ret
b=func(a[0])
for i in range(1,n):
  if b==func(a[i]):
    continue
  else:
    print(0)
    exit(0)
from fractions import gcd
lcmn=a[0]//2
for i in range(1,n):
    lcmn=(lcmn*a[i]//2)//gcd(lcmn,a[i]//2)
print((1+m//lcmn)//2)
Buggy python submission (verdict: Runtime Error):
n=int(input())
c=sorted(list(map(int,input().split())))
mod=pow(10,9)+7
# T=000000..とおいて計算し最後に2^nをかける。
# 各コストCiごとにそれが何回足されるかを求める。
# 一番大きいコストc[-1]の係数は必ず1にするのが最適。同様に一番小さいコストc[0]は必要な係数の中で一番大きなものをかけるのがいい。
ans=0
for i,ci in enumerate(c):
  l=i
  r=n-i
  b=pow(2,r-1,mod)+(r-1)*pow(2,r-2,mod) if r>0 else 1
  b*=pow(2,l,mod)
  ans+=ci*b
  ans%=mod
ans*=pow(2,n,mod)
print(ans%mod)


Fixed submission:
n=int(input())
c=sorted(list(map(int,input().split())))
#n=200000
#c=list(range(n))
mod=pow(10,9)+7
# T=000000..とおいて計算し最後に2^nをかける。
# 各コストCiごとにそれが何回足されるかを求める。
# 一番大きいコストc[-1]の係数は必ず1にするのが最適。同様に一番小さいコストc[0]は必要な係数の中で一番大きなものをかけるのがいい。
ans=0
for i,ci in enumerate(c):
  l=i
  r=n-i
  b=pow(2,r-1,mod)+(r-1)*pow(2,r-2,mod) if r>1 else 1
  b*=pow(2,l,mod)
  ans+=ci*b
  ans%=mod
ans*=pow(2,n,mod)
print(ans%mod)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
import bisect
# 解説の二分探索
# あるXを定め、X以上になる握手の組み合わせが何通りあるか計算。ちょうどM個以上になるXを探す
l,r=0,a[-1]*2
while r-l>1:
  x=(l+r)//2
  cnt=0
  for ai in a:
    cnt+=n-bisect.bisect_left(a,x-ai)
  # x以上がm個以上ある->xを増加
  [l,r]=[x,r] if cnt>=m else [l,x]
x=(l+r)//2
ans=[]
for ai in a:
  bi=bisect.bisect_left(a,x-ai)
  ans.extend([aj+ai for aj in a[bi:]])
ans.sort()
print(sum(ans[-m:]))


Fixed submission:

import sys
input = sys.stdin.readline
# 文字列をinput()した場合、末尾に改行が入るので注意
def main():
  n,m=map(int,input().split())
  a=sorted(list(map(int,input().split())))
  import bisect
  # 解説の二分探索
  # あるXを定め、X以上になる握手の組み合わせが何通りあるか計算。M個以上になる最大のXを探す
  # [l,r)半開区間
  l,r=0,a[-1]*2+1
  while r-l>1:
    x=(l+r)//2
    cnt=0
    for ai in a:
      cnt+=n-bisect.bisect_left(a,x-ai)
    # x以上がm個以上ある->x~r-1に求めるものがある
    if cnt>=m:
      l=x
    else:# x以上がm個未満ある->l~x-1に求めるものがある
      r=x
  x=(l+r)//2
  ans=0
  cnt=0
  a_=0
  cs_a=[0]
  for ai in a:
    a_+=ai
    cs_a.append(a_)
  for ai in a:
    bi=bisect.bisect_right(a,x-ai)
    cnt+=n-bi
    ans+=cs_a[-1]-cs_a[bi]+(n-bi)*ai
  print(ans+(m-cnt)*x)

if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())
Buggy python submission (verdict: Time Limit Exceeded):
import re
n=int(input())
s=input()
ans=0
for i in range(1000):
      a='00'+str(i)
      a=a[-3:]
      b=a[0]+r'\d*'+a[1]+r'\d*'+a[2]
      c=re.search(b,s)
      if c!=None:
            ans+=1
print(ans)

Fixed submission:
import re
n=int(input())
s=input()
ans=0
for i in range(1000):
      a='00'+str(i)
      a=a[-3:]
      s0=s
      m=s0.find(a[0])
      if m<0:
            continue
      s0=s0[m+1:]
      m=s0.find(a[1])
      if m<0:
            continue
      s0=s0[m+1:]
      m=s0.find(a[2])
      if m<0:
            continue
      ans+=1
print(ans)