Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
H,W,M=map(int,input().split())
L=[]
bh=[0]*(H+1)
bw=[0]*(W+1)
mh,mw=[0,[]],[0,[]]
for _ in range(M):
    h,w=map(int,input().split())
    L.append((h,w))
    bh[h]+=1
    bw[w]+=1
    if bh[h]>mh[0]:
        mh=[bh[h],[h]]
        nh=1
    elif bh[h]==mh[0]:
        mh[1].append(h)
        nh+=1
    if bw[w]>mw[0]:
        mw=[bw[w],[w]]
        nw=1
    elif bw[w]==mw[0]:
        mw[1].append(w)
        nw+=1
ans=mh[0]+mw[0]
n=0
if nh*nw<=M:
    for h,w in L:
        if h in mh[1] and w in mw[1]:
            n+=1
if n==nh*nw:
    ans-=1
print(ans)

Fixed submission:
H,W,M=map(int,input().split())
L=[]
bh=[0]*(H+1)
bw=[0]*(W+1)
for _ in range(M):
    h,w=map(int,input().split())
    L.append((h,w))
    bh[h]+=1
    bw[w]+=1
p,q=max(bh),max(bw)
num=len(list(filter(p.__eq__, bh)))*len(list(filter(q.__eq__,bw)))
num-=len(list(filter(lambda x: bh[x[0]]==p and bw[x[1]]==q, L)))
ans=p+q-1
if num>0:
    ans+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
H,W,M=map(int,input().split())
L=[]
bh=[0]*(H+1)
bw=[0]*(W+1)
mh,mw=[0,[]],[0,[]]
for _ in range(M):
    h,w=map(int,input().split())
    L.append((h,w))
    bh[h]+=1
    bw[w]+=1
    if bh[h]>mh[0]:
        mh=[bh[h],[h]]
    elif bh[h]==mh[0]:
        mh[1].append(h)
    if bw[w]>mw[0]:
        mw=[bw[w],[w]]
    elif bw[w]==mw[0]:
        mw[1].append(w)
ans=mh[0]+mw[0]
n=0
for h,w in L:
    if h in mh[1] and w in mw[1]:
        n+=1
if n==len(mh[1])*len(mw[1]):
    ans-=1
print(ans)

Fixed submission:
H,W,M=map(int,input().split())
L=[]
bh=[0]*(H+1)
bw=[0]*(W+1)
for _ in range(M):
    h,w=map(int,input().split())
    L.append((h,w))
    bh[h]+=1
    bw[w]+=1
p,q=max(bh),max(bw)
num=len(list(filter(p.__eq__, bh)))*len(list(filter(q.__eq__,bw)))
num-=len(list(filter(lambda x: bh[x[0]]==p and bw[x[1]]==q, L)))
ans=p+q-1
if num>0:
    ans+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
H,W,M=map(int,input().split())
L=[]
bh=[0]*(H+1)
bw=[0]*(W+1)
mh,mw=[0,[]],[0,[]]
for _ in range(M):
    h,w=map(int,input().split())
    L.append((h,w))
    bh[h]+=1
    bw[w]+=1
    if bh[h]>mh[0]:
        mh=[bh[h],[h]]
    elif bh[h]==mh[0]:
        mh[1].append(h)
    if bw[w]>mw[0]:
        mw=[bw[w],[w]]
    elif bw[w]==mw[0]:
        mw[1].append(w)
ans=mh[0]+mw[0]
n=0
for h,w in L:
    if h in mh[1] and w in mw[1]:
        n+=1
if n==len(mh[1])*len(mw[1]):
    ans-=1
print(ans)

Fixed submission:
H,W,M=map(int,input().split())
L=[]
bh=[0]*(H+1)
bw=[0]*(W+1)
for _ in range(M):
    h,w=map(int,input().split())
    L.append((h,w))
    bh[h]+=1
    bw[w]+=1
p,q=max(bh),max(bw)
num=len(list(filter(p.__eq__, bh)))*len(list(filter(q.__eq__,bw)))
num-=len(list(filter(lambda x: bh[x[0]]==p and bw[x[1]]==q, L)))
ans=p+q-1
if num>0:
    ans+=1
print(ans)
Buggy python submission (verdict: Runtime Error):
S=input()
ans=0
tmp=0
for s in S:
  if s='S':
    tmp+=1
  else:
    ans=max(ans,tmp)
    tmp=0
print(max(ans,tmp))

Fixed submission:
S=input()
ans=0
tmp=0
for s in S:
  if s=='R':
    tmp+=1
  else:
    ans=max(ans,tmp)
    tmp=0
print(max(ans,tmp))
Buggy python submission (verdict: Runtime Error):
N,K=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
A=[]
S=[]
p=2**N-1
for i in range(N):
  if p>>i&1:
    s=i+1
    tmp=[C[i]]
    while s!=P[i]:
      i=P[i]-1
      tmp.append(C[i])
      p^=1<<i
    A.append(tmp)
    S.append(sum(tmp))
ans=-1*(10**9)-1
for i in range(len(A)):
  a=A[i]
  n=len(a)
  s=S[i]
  for j in range(n):
    t=0
    k=n
    if K>n:
      if s > 0:
        k=K%n
        if :
          k=n
          t=s*(K//n-1)
        else:
          k=K%n
          t=s*(K//n)
    else:
      k=K
    for jj in range(j,k+j):
      if jj>=n:
        jj-=n
      t+=a[jj]
      ans=max(ans,t)
    ans=max(ans,t)
print(ans)


Fixed submission:
N,K=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
A=[]
S=[]
p=2**N-1
for i in range(N):
  if p>>i&1:
    s=i+1
    tmp=[C[i]]
    while s!=P[i]:
      i=P[i]-1
      tmp.append(C[i])
      p^=1<<i
    A.append(tmp)
    S.append(sum(tmp))
ans=-1*(10**9)-1
for i in range(len(A)):
  a=A[i]
  n=len(a)
  s=S[i]
  for j in range(n):
    t=0
    k=n
    if K>n:
      if s > 0:
        k=K%n
        if k==0:
          k=n
          t=s*(K//n-1)
        else:
          k=K%n
          t=s*(K//n)
    else:
      k=K
    for jj in range(j,k+j):
      if jj>=n:
        jj-=n
      t+=a[jj]
      ans=max(ans,t)
    ans=max(ans,t)
print(ans)
Buggy python submission (verdict: Runtime Error):
import sqrt
N,D=map(int,input())
ans=0
for _ in range(N):
  p,q=map(int,input().split())
  if math.sqrt(p**2+q**2)<=D:
    ans+=1
print(ans)

Fixed submission:
import math
N,D=map(int,input().split())
ans=0
for _ in range(N):
  p,q=map(int,input().split())
  if math.sqrt(p**2+q**2)<=D:
    ans+=1
print(ans)
Buggy python submission (verdict: Runtime Error):
N,K=map(int,input())
P=sorted(list(map(int,input().split())))
print(sum(P[:K]))

Fixed submission:
N,K=map(int,input().split())
P=sorted(list(map(int,input().split())))
print(sum(P[:K]))
Buggy python submission (verdict: Runtime Error):
N=int(input())
keta=1
a=26
while N>a:
  a*=26
  keta+=1
ans=""
for i in range(keta-1,0,-1):
  a=N//(26**i)-1
  N=N%(26**i)
  ans+=chr(ord('a')+a)
ans+=chr(ord('a')+N//(26**i))
print(ans)

Fixed submission:
N=int(input())
keta=1
a=26
ans=""
while N>0:
  N-=1
  ans+=chr(ord('a')+N%26)
  N=N//26
print(ans[::-1])

Buggy python submission (verdict: Runtime Error):
N=int(input())
keta=1
a=26
while N>a:
  a*=26
  keta+=1
ans=""
for i in range(keta-1,0,-1):
  a=N//(26**i)-1
  N=N%(26**i)
  ans+=chr(ord('a')+a)
ans+=chr(ord('a')+N//(26**i))
print(ans)

Fixed submission:
N=int(input())
keta=1
a=26
ans=""
while N>0:
  N-=1
  ans+=chr(ord('a')+N%26)
  N=N//26
print(ans[::-1])
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
import sys

def input():
  return sys.stdin.readline()

N=int(input())
A=sorted(list(map(int,input().split())))
Q=int(input())
for i in range(Q):
  b,c=map(int,input().split())
  l=bisect.bisect_left(A,b)
  r=bisect.bisect_right(A,b)
  for j in range(l,r):
    A[j]=c
  print(sum(A))


Fixed submission:
import sys

def input():
  return sys.stdin.readline()

N=int(input())
A=list(map(int,input().split()))
B=[0]*(10**5)
for a in A:
  B[a-1]+=1
s=sum(A)
Q=int(input())
for i in range(Q):
  b,c=map(int,input().split())
  bb,bc=B[b-1],B[c-1]
  B[c-1]+=bb
  B[b-1]=0
  s+=bb*c-bb*b
  print(s)

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

def input():
  return sys.stdin.readline()

N=int(input())
A=sorted(list(map(int,input().split())))
Q=int(input())
for i in range(Q):
  b,c=map(int,input().split())
  l=bisect.bisect_left(A,b)
  r=bisect.bisect_right(A,b)
  for j in range(l,r):
    A[j]=c
  print(sum(A))

Fixed submission:
import sys

def input():
  return sys.stdin.readline()

N=int(input())
A=list(map(int,input().split()))
B=[0]*(10**5)
for a in A:
  B[a-1]+=1
s=sum(A)
Q=int(input())
for i in range(Q):
  b,c=map(int,input().split())
  bb,bc=B[b-1],B[c-1]
  B[c-1]+=bb
  B[b-1]=0
  s+=bb*c-bb*b
  print(s)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N=int(input())
A=sorted(list(map(int,input().split())))
Q=int(input())
for i in range(Q):
  b,c=map(int,input().split())
  l=bisect.bisect_left(A,b)
  r=bisect.bisect_right(A,b)
  for j in range(l,r):
    A[j]=c
  print(sum(A))

Fixed submission:
import sys

def input():
  return sys.stdin.readline()

N=int(input())
A=list(map(int,input().split()))
B=[0]*(10**5)
for a in A:
  B[a-1]+=1
s=sum(A)
Q=int(input())
for i in range(Q):
  b,c=map(int,input().split())
  bb,bc=B[b-1],B[c-1]
  B[c-1]+=bb
  B[b-1]=0
  s+=bb*c-bb*b
  print(s)
Buggy python submission (verdict: Runtime Error):
a=360/n
b=a-360//n
print(int(n*360/math.gcd(n,360)/n))

Fixed submission:
import math
n=int(input())
a=360/n
b=a-360//n
print(int(n*360/math.gcd(n,360)/n))
Buggy python submission (verdict: Runtime Error):
X,N=map(int,input().split())
p=[]
if N>0:
  p=list(map(int,input().split()))
  L=[abs(X-i) for i in P]
  l=min(L)
  if X-l in P:
    print(X-l)
  else:
    print(X+l)
else:
  print(X)

Fixed submission:
X,N=map(int,input().split())
if N>0:
  P=list(map(int,input().split()))
  for i in range(N+1):
    if X-i not in P:
      print(X-i)
      break
    elif X+i not in P:
      print(X+i)
      break
else:
  print(X)
Buggy python submission (verdict: Time Limit Exceeded):
limit=10**18
n=int(input())
A=list(map(int,input().split()))
ans=1
for a in A:
  ans*=a
print(ans if ans<=limit else -1)

Fixed submission:
limit=10**18
n=int(input())
A=list(map(int,input().split()))
ans=1
if 0 in A:
  ans=0
else:
  for a in A:
    ans*=a
    if ans > limit:
      ans=-1
      break
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
MOD=998244353
N,M,K=map(int,input().split())

f,invf=[1],[1]*N
for i in range(1,N):
    f.append(f[i-1]*i)
invf[N-1]=pow(f[N-1],MOD-2,MOD)
for i in range(N-1,0,-1):
    invf[i-1]=(invf[i]*i)%MOD
ans=0
c=[1]*(N)
for i in range(1,N):
    c[i]=c[i-1]*(M-1)%MOD
for i in range(K+1):
    ans+=M*c[N-i-1]*f[N-1]*invf[N-i-1]*invf[i]
    ans%=MOD
print(ans)

Fixed submission:
mod=998244353

class Combination:
    def __init__(self, N):
        self.fac = [1] * (N + 1)
        for i in range(1, N + 1):
            self.fac[i] = (self.fac[i - 1] * i) % mod
        self.invmod = [1] * (N + 1)
        self.invmod[N] = pow(self.fac[N], mod - 2, mod)
        for i in range(N, 0, -1):
            self.invmod[i - 1] = (self.invmod[i] * i) % mod
 
    def calc(self, n, k):  # nCk
        return self.fac[n] * self.invmod[k] % mod * self.invmod[n - k] % mod

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

C=Combination(N)
ans=0
c=[1]*(N)
for i in range(1,N):
    c[i]=c[i-1]*(M-1)%mod
for i in range(K+1):
    tmp=M*c[N-i-1]*C.calc(N-1,N-i-1)%mod
    ans=(ans+tmp)%mod
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def pow(x,n,mod):
    ans = 1
    while n>0:
        if n&1==1:
            ans *= x
            ans%=mod
        x*=x
        x%=mod
        n = n>>1
    return ans

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

ans=M*pow(M-1,N-1,MOD)%MOD
a=1
b=1
for i in range(1,K+1):
    a*=N-i
    b*=i
    ans+=M*pow(M-1,N-i-1,MOD)*int(a//b)
    ans%=MOD
print(ans)

Fixed submission:
mod=998244353

class Combination:
    def __init__(self, N):
        self.fac = [1] * (N + 1)
        for i in range(1, N + 1):
            self.fac[i] = (self.fac[i - 1] * i) % mod
        self.invmod = [1] * (N + 1)
        self.invmod[N] = pow(self.fac[N], mod - 2, mod)
        for i in range(N, 0, -1):
            self.invmod[i - 1] = (self.invmod[i] * i) % mod
 
    def calc(self, n, k):  # nCk
        return self.fac[n] * self.invmod[k] % mod * self.invmod[n - k] % mod

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

C=Combination(N)
ans=0
c=[1]*(N)
for i in range(1,N):
    c[i]=c[i-1]*(M-1)%mod
for i in range(K+1):
    tmp=M*c[N-i-1]*C.calc(N-1,N-i-1)%mod
    ans=(ans+tmp)%mod
print(ans)
Buggy python submission (verdict: Runtime Error):
N,K=map(int,input().split())
s={i+1 for i in range(N)}
t={}
for i in range(K):
  input()
  t|=set(map(int,input().split()))
print(len(s-t))

Fixed submission:
N,K=map(int,input().split())
s={i+1 for i in range(N)}
t=set()
for i in range(K):
  input()
  t|=set(map(int,input().split()))
print(len(s-t))
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))
np,nm=[],[]
for i in range(N):
    np.append(A[i]+i)
    nm.append(i-A[i])
sp,sm=sorted(np),sorted(nm)
ans=0
for i in range(N):
    p,m=np[i],nm[i]
    l,r=0,N
    while not l+1==r:
        x=(l+r)//2
        if sm[x]<=p:
            l=x
        else:
            r=x
    while sm[l]==p and l>=0:
        ans+=1
        l-=1
    l,r=0,N
    while not l+1==r:
        x=(l+r)//2
        if sp[x]<=m:
            l=x
        else:
            r=x
    while sp[l]==m and l>=0:
        ans+=1
        l-=1
print(ans//2)

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
np,nm=[],[]
for i in range(N):
    np.append(A[i]+i)
    nm.append(i-A[i])
sp,sm=sorted(np),sorted(nm)
ans=0
for i in range(N):
    p,m=np[i],nm[i]
    l,r=-1,N
    while not l+1==r:
        x=(l+r)//2
        if sm[x]<=p:
            l=x
        else:
            r=x
    tmp=l
    l,r=-1,N
    while not l+1==r:
        x=(l+r)//2
        if sm[x]<p:
            l=x
        else:
            r=x
    ans+=tmp-l
    l,r=-1,N
    while not l+1==r:
        x=(l+r)//2
        if sp[x]<=m:
            l=x
        else:
            r=x
    tmp=l
    l,r=-1,N
    while not l+1==r:
        x=(l+r)//2
        if sp[x]<m:
            l=x
        else:
            r=x
    ans+=tmp-l
print(ans//2)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))
np,nm=[],[]
for i in range(N):
    np.append(A[i]+i)
    nm.append(i-A[i])
sp,sm=sorted(np),sorted(nm)
ans=0
for i in range(N):
    p,m=np[i],nm[i]
    l,r=0,N
    while not l+1==r:
        x=(l+r)//2
        if sm[x]<=p:
            l=x
        else:
            r=x
    while sm[l]==p and l>=0:
        ans+=1
        l-=1
    l,r=0,N
    while not l+1==r:
        x=(l+r)//2
        if sp[x]<=m:
            l=x
        else:
            r=x
    while sp[l]==m and l>=0:
        ans+=1
        l-=1
print(ans//2)

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
np,nm=[],[]
for i in range(N):
    np.append(A[i]+i)
    nm.append(i-A[i])
sp,sm=sorted(np),sorted(nm)
ans=0
for i in range(N):
    p,m=np[i],nm[i]
    l,r=-1,N
    while not l+1==r:
        x=(l+r)//2
        if sm[x]<=p:
            l=x
        else:
            r=x
    tmp=l
    l,r=-1,N
    while not l+1==r:
        x=(l+r)//2
        if sm[x]<p:
            l=x
        else:
            r=x
    ans+=tmp-l
    l,r=-1,N
    while not l+1==r:
        x=(l+r)//2
        if sp[x]<=m:
            l=x
        else:
            r=x
    tmp=l
    l,r=-1,N
    while not l+1==r:
        x=(l+r)//2
        if sp[x]<m:
            l=x
        else:
            r=x
    ans+=tmp-l
print(ans//2)
Buggy python submission (verdict: Runtime Error):
K=int(input().split())
A,B=map(int,input().split())
n=A//K
print("OK" if A<=K*n<=B or K*(n+1)<=B else "NG")

Fixed submission:
K=int(input())
A,B=map(int,input().split())
n=A//K
print("OK" if A<=K*n<=B or K*(n+1)<=B else "NG")
Buggy python submission (verdict: Time Limit Exceeded):
S=input()
ans,n=0,len(S)
dp=[0]*(2019)
s,dp[0],k=0,1,1
for i in range(1,n+1):
  s=(s+int(S[-i])*k)%2019
  k*=10
  ans+=dp[s]
  dp[s]+=1
print(ans)

Fixed submission:
S=input()
ans,n=0,len(S)
dp=[0]*(2019)
s,dp[0],k=0,1,1
for i in range(1,n+1):
  s=(s+int(S[-i])*k)%2019
  k=(k*10)%2019
  ans+=dp[s]
  dp[s]+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S=input()
ans,n=0,len(S)
dp=[0]*(2019)
s,dp[0],k=0,1,1
for i in range(1,n+1):
  s=(s+int(S[-i])*k)%2019
  k*=10
  ans+=dp[s]
  dp[s]+=1
print(ans)

Fixed submission:
S=input()
ans,n=0,len(S)
dp=[0]*(2019)
s,dp[0],k=0,1,1
for i in range(1,n+1):
  s=(s+int(S[-i])*k)%2019
  k=(k*10)%2019
  ans+=dp[s]
  dp[s]+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S=input()
ans,n=0,len(S)
dp=[0]*(2019)
s,dp[0]=0,1
for i in range(1,n+1):
  s=(s+int(S[-i])*10**(i-1))%2019
  ans+=dp[s]
  dp[s]+=1
print(ans)

Fixed submission:
S=input()
ans,n=0,len(S)
dp=[0]*(2019)
s,dp[0],k=0,1,1
for i in range(1,n+1):
  s=(s+int(S[-i])*k)%2019
  k=(k*10)%2019
  ans+=dp[s]
  dp[s]+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S=input()
ans,n=0,len(S)
dp=[0]*(2019)
s,dp[0]=0,1
for i in range(1,n+1):
  s+=int(S[-i])*(10**(i-1))
  ans+=dp[s%2019]
  dp[s%2019]+=1
print(ans)

Fixed submission:
S=input()
ans,n=0,len(S)
dp=[0]*(2019)
s,dp[0],k=0,1,1
for i in range(1,n+1):
  s=(s+int(S[-i])*k)%2019
  k=(k*10)%2019
  ans+=dp[s]
  dp[s]+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S=input()
ans,n=0,len(S)
dp=[0]*(2019)
s,dp[0]=0,1
for i in range(1,n+1):
  s+=int(S[-i])*(10**(i-1))
  dp[s%2019]+=1
for i in range(2019):
  m=dp[i]
  ans+=m*(m-1)//2
print(ans)

Fixed submission:
S=input()
ans,n=0,len(S)
dp=[0]*(2019)
s,dp[0],k=0,1,1
for i in range(1,n+1):
  s=(s+int(S[-i])*k)%2019
  k=(k*10)%2019
  ans+=dp[s]
  dp[s]+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S=input()
ans,n=0,len(S)
dp=[0]*(n+1)
s=0
for i in range(1,n+1):
  s+=int(S[-i])*(10**(i-1))
  dp[n-i]=s%2019
for i in range(n-3):
  for j in range(i+3,n+1):
    if dp[i]==dp[j]:
      ans+=1
print(ans)

Fixed submission:
S=input()
ans,n=0,len(S)
dp=[0]*(2019)
s,dp[0],k=0,1,1
for i in range(1,n+1):
  s=(s+int(S[-i])*k)%2019
  k=(k*10)%2019
  ans+=dp[s]
  dp[s]+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S=input()
ans=0
N=len(S)
for i in range(N-2):
  for j in range(i+4,N+1):
    if int(S[i:j])%2019==0:
      ans+=1
print(ans)

Fixed submission:
S=input()
ans,n=0,len(S)
dp=[0]*(2019)
s,dp[0],k=0,1,1
for i in range(1,n+1):
  s=(s+int(S[-i])*k)%2019
  k=(k*10)%2019
  ans+=dp[s]
  dp[s]+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S=input()
ans=0
N=len(S)
for i in range(N-2):
  s=S[i:i+3]
  for j in range(i+3,N):
    s+=S[j]
    if int(s)%2019==0:
      ans+=1
print(ans)

Fixed submission:
S=input()
ans,n=0,len(S)
dp=[0]*(2019)
s,dp[0],k=0,1,1
for i in range(1,n+1):
  s=(s+int(S[-i])*k)%2019
  k=(k*10)%2019
  ans+=dp[s]
  dp[s]+=1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=input()
ans=0
for i in range(N-2):
  a=S[i]
  for j in range(i+1,N-1):
    b=S[j]
    for k in range(j+1,N):
      c=S[k]
      if j-i!=k-j and a!=b and a!=c and b!=c:
        ans+=1
print(ans)

Fixed submission:
N=int(input())
S=input()
ans,r,g,b=0,0,0,0
for s in S:
  if s=='R':
    r+=1
  elif s=='G':
    g+=1
  elif s=='B':
    b+=1
ans=r*g*b
for i in range(N-2):
  a=S[i]
  for j in range(i+1,N-1):
    if 2*j-i>=N:
      break
    b,c=S[j],S[j+j-i]
    if a!=b and b!=c and c!=a:
      ans-=1
print(ans)
Buggy python submission (verdict: Runtime Error):
K=int(input())

p=1
dp,old=[[1]*10],[0,1]
n=9
while K>n:
  old=dp[p-1]
  tmp=[0]*10
  for i in range(1,9):
    tmp[i]=old[i-1]+old[i]+old[i+1]
  tmp[9]=old[8]+old[9]
  tmp[0]=old[0]+old[1]
  dp.append(tmp)
  p+=1
  n+=sum(tmp[1:])

ans=0
n-=sum(tmp[1:])
K-=n
c=2
for i in range(p-1,-1,-1):
  if c!=0:
    c-=1
  while K>dp[i][c]:
    K-=dp[i][c]
    c+=1
  ans+=c*10**i
print(ans)

Fixed submission:
K=int(input())

if K<=9:
  print(K)
else:
  p=1
  dp,old=[[1]*10],[0,1]
  n=9
  while K>n:
    old=dp[p-1]
    tmp=[0]*10
    for i in range(1,9):
      tmp[i]=old[i-1]+old[i]+old[i+1]
    tmp[9]=old[8]+old[9]
    tmp[0]=old[0]+old[1]
    dp.append(tmp)
    p+=1
    n+=sum(tmp[1:])

  ans=0
  n-=sum(tmp[1:])
  K-=n
  c=2
  for i in range(p-1,-1,-1):
    if c!=0:
      c-=1
    while K>dp[i][c]:
      K-=dp[i][c]
      c+=1
    ans+=c*10**i
  print(ans)
Buggy python submission (verdict: Runtime Error):
K,N=map(int,input().split())
A=list(map(int,input().split()))
l=[]
p = A[-1]-K
for a in A:
  l.append(a-l)
  p=a
print(sum(l)-max(l))

Fixed submission:
K,N=map(int,input().split())
A=list(map(int,input().split()))
l=[]
p = A[-1]-K
for a in A:
  l.append(a-p)
  p=a
print(sum(l)-max(l))
Buggy python submission (verdict: Time Limit Exceeded):
H,W,K=map(int,input().split())
S=[[int(s) for s in input()] for i in range(H)]

ans=1000000
for i in range(2**(H-1)):
    tmp=0
    L=[]
    for j in range(H-1):
        if i>>j&1:
            L.append(j)
    tmp+=len(L)
    L.append(H-1)
    c=[0]*len(L)
    for k in range(W):
        h=0
        c1=[0]*len(L)
        for l in range(len(L)):
            for m in range(h,L[l]+1):
                c1[l]+=S[m][k]
            h=L[l]+1
        p=0
        for l in range(len(L)):
            if c1[l]>K:
                p=2
                break
            elif c[l]+c1[l]>K:
                p=1
            else:
                c[l]+=c1[l]
        if p==2:
            break
        elif p==1:
            c=[i for i in c1]
            tmp+=1
    else:
        ans=min(ans,tmp)
print(ans)

Fixed submission:
H,W,K=map(int,input().split())
S=[[int(s) for s in input()] for i in range(H)]

ans=1000000
for i in range(2**(H-1)):
    tmp=0
    L=[]
    for j in range(H-1):
        if i>>j&1:
            L.append(j)
    tmp+=len(L)
    L.append(H-1)
    c=[0]*len(L)
    for k in range(W):
        h=0
        c1=[0]*len(L)
        for l in range(len(L)):
            for m in range(h,L[l]+1):
                c1[l]+=S[m][k]
            h=L[l]+1
        p=0
        for l in range(len(L)):
            if c1[l]>K:
                p=2
                break
            elif c[l]+c1[l]>K:
                p=1
            else:
                c[l]+=c1[l]
        if p==2:
            break
        elif p==1:
            c=[i for i in c1]
            tmp+=1
    else:
        ans=min(ans,tmp)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq

N,K=map(int,input().split())
A=list(map(int,input().split()))
h=[]
heapq.heapify(h)
for i in range(N-1):
  a=A[i]
  for j in range(i+1,N):
    heapq.heappush(h,a*A[j])
for _ in range(K-1):
  heapq.heappop(h)
print(heapq.heappop(h))

Fixed submission:
N,K=map(int,input().split())
A=sorted(map(int,input().split()))
x=0
r=10**18+1
l=-(10**18)
while l+1<r:
    x=(l+r)//2
    k=0
    for a in A:
        if a<0:
            ll,rr=-1,N
            while ll+1<rr:
                c=(rr+ll)//2
                if x>a*A[c]:
                    rr=c
                else:
                    ll=c
            k+=N-rr
        else:
            ll,rr=-1,N
            while ll+1<rr:
                c=(rr+ll)//2
                if x>a*A[c]:
                    ll=c
                else:
                    rr=c
            k+=rr
        if x>a**2:
            k-=1
    k//=2
    if k<K:
        l=x
    else:
        r=x
print(l)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

N,K=map(int,input().split())
A=sorted(map(int,input().split()))
for i in range(N):
    if A[i]>=0:
        break
minus=i
for i in range(i,N):
    if A[i]>0:
        break
zero=i-minus
plus=N-zero-minus
if minus*plus>=K:
    h=[]
    heapq.heapify(h)
    for a in A[:minus]:
        for b in A[minus+zero:]:
            heapq.heappush(h,a*b)
    for _ in range(K-1):
        heapq.heappop(h)
    print(heapq.heappop(h))
    exit()
K-=minus*plus
if zero!=0:
    for i in range(zero):
        K-=N-zero+i
    if K<=0:
        print(0)
        exit()
h=[]
heapq.heapify(h)
for i in range(minus+zero,N-1):
    for j in range(i+1,N):
        heapq.heappush(h,A[i]*A[j])
for i in range(minus-1):
    for j in range(i+1,minus):
        heapq.heappush(h,A[i]*A[j])
for _ in range(K-1):
    heapq.heappop(h)
print(heapq.heappop(h))


Fixed submission:
N,K=map(int,input().split())
A=sorted(map(int,input().split()))
x=0
r=10**18+1
l=-(10**18)
while l+1<r:
    x=(l+r)//2
    k=0
    for a in A:
        if a<0:
            ll,rr=-1,N
            while ll+1<rr:
                c=(rr+ll)//2
                if x>a*A[c]:
                    rr=c
                else:
                    ll=c
            k+=N-rr
        else:
            ll,rr=-1,N
            while ll+1<rr:
                c=(rr+ll)//2
                if x>a*A[c]:
                    ll=c
                else:
                    rr=c
            k+=rr
        if x>a**2:
            k-=1
    k//=2
    if k<K:
        l=x
    else:
        r=x
print(l)
Buggy python submission (verdict: Runtime Error):
N=int(input())
A=list(map(int,input()))
S=set(A)
print("YES" if len(A)==len(S) else "NO")

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
S=set(A)
print("YES" if len(A)==len(S) else "NO")

Buggy python submission (verdict: Runtime Error):
N=int(input())
A=list(map(int,input()))
B=[]
p=True
for a in A:
  if a in B:
    p = False
    break
  else:
    B.append(a)
print("Yes" if p else "No")

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
S=set(A)
print("YES" if len(A)==len(S) else "NO")