Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p03086 (python)

Fixed submission:
def main():
	# a,b,k = map(int,input().split())
	# n,k = map(int,input().split())
	s = list(str(input()))
	# a = list(map(int,input().split()))
	# rsp = list(str(input()))
	# l = [list(map(int, input().split())) for _ in range(n-1)]
	# s = list(s)
	avoid = 0
	ans = 0
	ans_rec = []
	for i in range(len(s)):
		if s[i] == "A" or s[i] == "T" or s[i] == "G" or s[i] == "C":
			# print("when i = {} is true".format(i))
			ans += 1
		else:
			ans_rec.append(ans)
			ans = 0
	ans_rec.append(ans)
			
	print(max(ans_rec))

 
if __name__ == '__main__':
	main()

Buggy submission (verdict: Runtime Error):
def main():
	# a,b,k = map(int,input().split())
	# n,k = map(int,input().split())
	s = list(str(input()))
	# a = list(map(int,input().split()))
	# rsp = list(str(input()))
	# l = [list(map(int, input().split())) for _ in range(n-1)]
	# s = list(s)
	avoid = 0
	ans = 0
	ans_rec = []
	for i in range(len(s)):
		if s[i] == "A" or s[i] == "T" or s[i] == "G" or s[i] == "C":
			# print("when i = {} is true".format(i))
			ans += 1
		else:
			ans_rec.append(ans)
			ans = 0
			
	print(max(ans_rec))

 
if __name__ == '__main__':
	main()
Problem p02609 (python)

Fixed submission:
def f(n):
    cnt = 0
    while n:
        buf = n
        pc = 0
        while buf:
            pc += buf%2
            buf //= 2
        n = n%pc
        cnt += 1
    return cnt

N = int(input())
X = input()

v1, v2 = 0, 0
cnt = X.count("1")
for i, j in enumerate(X[::-1]):
    if j=="1":
        v1 += pow(2, i, cnt+1)
        v1 %= (cnt+1)

        if cnt>1:
            v2 += pow(2, i, cnt-1)
            v2 %= (cnt-1)

for i in range(N):
    p = N-i-1
    buf = 0
    c2 = 0
    if X[i]=="0":
        c2 = cnt+1
        buf = (v1+pow(2, p, c2))%c2
        print(f(buf)+1)
    else:
        c2 = cnt-1
        if c2>0:
            buf = (v2-pow(2, p, c2))%c2
            print(f(buf)+1)
        else:
            print(0)

Buggy submission (verdict: Runtime Error):
N = int(input())
X = input()

def f(n, first):
    cnt = 1
    n %= first
    while n!=0:
        pc = bin(n).count("1")
        n = n%pc
        cnt += 1
    return cnt

v = 0
for i, j in enumerate(X[::-1]):
    if j=="1":
        v += 2**i
cnt = X.count("1")

for i in range(N):
    p = N-i-1
    buf = 0
    c2 = 0
    if X[i]=="0":
        buf = v+2**p
        c2 = cnt+1
    else:
        buf = v-2**p
        c2 = cnt-1
    print(f(buf, c2))
Problem p02632 (python)

Fixed submission:
MOD = 10**9+7
K = int(input())
S = input()
N = len(S)

n = N+K
fac = [1]*(n+1)
rev = [1]*(n+1)
 
for i in range(1,n+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD

ans = 0
for i in range(K+1):
    ans += pow(26, K-i, MOD) * pow(25, i, MOD) * comb(N+i-1, i)
    ans %= MOD
print(ans)

Buggy submission (verdict: Runtime Error):
def solve():
    K = int(input())
    S = input()
    N = len(S)

    MOD = 10**9+7
    n = N+K
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    
    for i in range(1,n+1):
    fac[i] = i*fac[i-1]%MOD
    rev[i] = pow(fac[i], MOD-2, MOD)
    
    comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD

    ans = 0
    for i in range(K+1):
        ans += pow(26, K-i, MOD) * pow(25, i, MOD) * comb(N+i-1, i)
        ans %= MOD
    print(ans)


solve()
Problem p02677 (python)

Fixed submission:
from math import cos, radians, sqrt

A, B, H, M = map(int, input().split())
rad = 0 if H==0 and M==0 else radians(abs(360/(720/(60*H+M))-6*M))
ans = sqrt((A**2)+(B**2)-2*A*B*cos(rad))
print(ans)

Buggy submission (verdict: Runtime Error):
from math import cos, radians, sqrt

A, B, H, M = map(int, input().split())
rad = radians(abs(360/(720/(60*H+M))-6*M))
ans = sqrt((A**2)+(B**2)-2*A*B*cos(rad))
print(ans)
Problem p02722 (python)

Fixed submission:
N = int(input())
ans = set()

def check(N, k):
    if k<2:
        return False
    N //= k
    while N:
        if (N-1)%k==0:
            return True
        if N%k:
            return False
        N //= k
    return False


for k in range(1, int(N**0.5)+1):
    if (N-1)%k==0:
        k1, k2 = k, (N-1)//k
        ans.add(k1)
        ans.add(k2)
    if N%k==0:
        k1, k2 = k, N//k
        if check(N, k1):
            ans.add(k1)
        if check(N, k2):
            ans.add(k2)

ans.remove(1)
print(len(ans))

Buggy submission (verdict: Runtime Error):
N = int(input())
ans = set()

def check(N, k):
    if k<2:
        return False
    N //= k
    while N:
        if (N-1)%k==0:
            return True
        if N%k:
            return False
        N //= k

for k in range(1, int(N**0.5)+1):
    if (N-1)%k==0:
        ans.add(k)
        ans.add((N-1)//k)
    if N%k==0:
        if check(N, k):
            ans.add(k1)
        if check(N, N//k):
            ans.add(k2)

ans.remove(1)
print(len(ans))
Problem p02765 (python)

Fixed submission:
N, R = map(int, input().split())
print(R+100*(10-N) if N<10 else R)

Buggy submission (verdict: Runtime Error):
N, R = map(int, input().split())
print(R+100*(10-K) if N<10 else R)

Buggy submission (verdict: Runtime Error):
N, R = map(int, input().split())
if N<10:
  print(R+100*(10-K))
else:
  print(R)
Problem p02775 (python)

Fixed submission:
s = input()[::-1]
size = len(s)
s += "4"

ans = 0
bef = 0

for i in range(size):
    v1 = int(s[i])
    v2 = int(s[i+1])
    if v1+bef>=6 or (v1+bef>=5 and v2>=5):
        ans += 10-(v1+bef)
        bef = 1
    else:
        ans += (v1+bef)
        bef = 0

ans += bef
print(ans)

Buggy submission (verdict: Runtime Error):
s = input()[::-1]
size = len(s)
s += "9"

ans = 0
bef = 0

for i in range(size):
    v1 = int(s[i])
    v2 = int(s[i+1])
    if v1+bef>=6 or (v1+bef>=5 and v2>=5):
        ans += 10-(v1+bef)
        bef = 1
    else:
        ans += (v1+bef)
        bef = 0

ans += (v+bef)//10
print(ans)
Problem p02782 (python)

Fixed submission:
def solve():
    r1, c1, r2, c2 = map(int, input().split())

    MOD = 10**9+7
    n = r2+c2+2
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    
    for i in range(1,n+1):
      fac[i] = i*fac[i-1]%MOD
      rev[i] = pow(fac[i], MOD-2, MOD)
    
    comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD

    def f(r, c):
        return comb(r+c+2, c+1)

    ans = f(r2, c2) - f(r2, c1-1) - f(r1-1, c2) + f(r1-1, c1-1)
    ans %= MOD

    print(ans)


if __name__ == "__main__":
    solve()

Buggy submission (verdict: Runtime Error):
r1, c1, r2, c2 = map(int, input().split())

MOD = 10**9+7
n = max(r1, c1, r2, c2)
fac = [1]*(n+1)
rev = [1]*(n+1)
 
for i in range(1,n+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD

w = r2 - r1
h = c2 - c1
X, Y = 0, 0
ans = comb(c1+r1, r1)
for i in range(c1+1, c2+1):
    ans += comb(i+r1, r1)
    X += (h-(i-(c1+1)))*comb(i+r1, r1)
for i in range(r1+1, r2+1):
    ans += comb(i+c1, c1)
    Y += (w-(i-(r1+1)))*comb(i+c1, c1)
ans += w*X+h*Y
ans %= MOD
print(ans)

Buggy submission (verdict: Runtime Error):
MOD = 10**9+7
n = 10**5
fac = [1]*(n+1)
rev = [1]*(n+1)
 
for i in range(1,n+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD

r1, c1, r2, c2 = map(int, input().split())
w = r2 - r1
h = c2 - c1
X, Y = 0, 0
ans = comb(c1+r1, r1)
for i in range(c1+1, c2+1):
    ans += comb(i+r1, r1)
    X += (h-(i-(c1+1)))*comb(i+r1, r1)
for i in range(r1+1, r2+1):
    ans += comb(i+c1, c1)
    Y += (w-(i-(r1+1)))*comb(i+c1, c1)
ans += w*X+h*Y
ans %= MOD
print(ans)
Problem p02786 (python)

Fixed submission:
def f(x):
    if x==1:return 1
    return 2*f(x//2)+1

H = int(input())
print(f(H))

Buggy submission (verdict: Runtime Error):
def f(x):
    if x==1:return 1
    return 2*f(x//2)+1

H = int(input())
print(H(n))
Problem p02803 (python)

Fixed submission:
H, W = map(int, input().split())
m = [list(input()) for _ in range(H)]
inf = 10**3

V = H*W
maze = [[inf]*V for _ in range(V)]

for i in range(V):
    maze[i][i] = 0

for py in range(H):
    for px in range(W):
        if m[py][px] == "#":
            continue
        candidate = [(px+1, py), (px-1, py), (px, py+1), (px, py-1)]
        for x, y in candidate:
            if not (0<=x<W and 0<=y<H):continue
            if m[y][x] == "#":
                continue
            maze[W*py+px][W*y+x] = 1

for k in range(V):
    for i in range(V):
        for j in range(V):
            maze[i][j] = min(maze[i][j], maze[i][k]+maze[k][j])

print(max([j for i in maze for j in i if j!=inf]))

Buggy submission (verdict: Runtime Error):
from collections import deque
import sys
import numpy as np

input = sys.stdin.readline
H, W = map(int, input().split())

maze = np.zeros((H, W), dtype='int')


for y in range(H):
    for x, s in enumerate(input()):
        if s=="#":
            maze[y][x] = 1


def bfs(x, y):
    queue = deque([(x, y, 0)])
    visited = np.zeros_like(maze, dtype='int') 

    max_cost = 0
    while queue:
        px, py, cost = queue.popleft()
        max_cost = max(max_cost, cost)

        candidate = ((px + 1, py), (px - 1, py), (px, py + 1), (px, py - 1))
        visited[py][px] = 1
        for cx, cy in candidate:
            if 0 <= cx < W and 0 <= cy < H and visited[cy][cx] == 0 and maze[cy][cx] == 0:
                queue.append((cx, cy, cost + 1))
    
    return max_cost


ans = 0
for y in range(H):
    for x in range(W):
        if maze[y][x] == 0:
            ans = max(ans, bfs(x, y))

print(ans)
Problem p02814 (python)

Fixed submission:
from fractions import gcd
from functools import reduce

N, M = map(int, input().split())
*a, = map(int, input().split())
lcm = reduce(lambda x,y:x*y//gcd(x,y), a)

for i in map(lambda x:lcm//x, a):
    if i%2==0:
        print(0)
        break
else:
    start = lcm//2
    print((M-start)//lcm+1)

Buggy submission (verdict: Runtime Error):
from fractions import gcd
from functools import reduce

N, M = map(int, input().split())
*a, = map(int, input().split())
lcm = reduce(lambda x,y:x*y//gcd(x,y), a)

m = 10**9
for i in map(lambda x:lcm//x, a):
    if i%2==0:
        print(0)
        break
    m = min(m, i)
else:
    start = int(lcm*0.5)
    print((M-start)//lcm+1)

Buggy submission (verdict: Runtime Error):
from fractions import gcd
from functools import reduce

N, M = map(int, input().split())
*a, = map(int, input().split())
lcm = reduce(lambda x,y:x*y//gcd(x,y), a)

m = 10**9
for i in map(lambda x:lcm//x, a):
    if i%2==0:
        print(0)
        break
    m = min(m, i)
else:
    if m==1:
        start = int(lcm*1.5)
    else:
        start = int(lcm*0.5)

    print((M-start)//lcm+1)
Problem p02837 (python)

Fixed submission:
from itertools import product

N = int(input())
c = product(range(2), repeat=N)
d = [[] for _ in range(N)]

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


ans = 0
for l in c:
    o = [None]*N
    is_conflict = False
    for i, j in enumerate(l):
        if j==0:continue
        for x, y in d[i]:
            if (o[x-1]!=None and o[x-1]!=y) or l[x-1]!=y:
                is_conflict = True
                break
            o[x-1] = y
        if is_conflict == True:
            break
    else:
        ans = max(ans, sum(l))

print(ans)

Buggy submission (verdict: Runtime Error):
from itertools import product

N = int(input())
c = product(range(2), repeat=N)
d = [[] for _ in range(N)]

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


ans = 0
for l in c:
    o = [None]*N
    is_conflict = False
    for i, j in enumerate(l):
        if j==0:continue
        for x, y in d[i]:
            if (o[x-1]!=None and o[x-1]!=y) or l[x-1]!=y:
                is_conflict = True
                break
            o[x-1] = y
        if is_conflict == True:
            break
    else:
        ans = mas(ans, sum(l))

print(ans)
Problem p02838 (python)

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

d1 = [[0]*60 for _ in range(N+1)]
mod = 10**9+7

for i, n in enumerate(A, start=1):
    for j in range(60):
        d1[i][j] = d1[i-1][j] + ((n>>j)&1)

ans = 0
for i, n in enumerate(A, start=1):
    for j in range(60):
        a = d1[N][j]-d1[i][j] # 1
        if (n>>j)&1:
            a = N-a-i # 0

        ans += a*(1<<j)
    ans %= mod

print(ans)

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

d1 = [[0]*60 for _ in range(N+1)]
mod = 10**9+7

for i, n in enumerate(A, start=1):
    for j in range(60):
        d1[i][j] = d1[i-1][j] + n%2
        n//=2

ans = 0
for i, n in enumerate(A, start=1):
    for j in range(60):
        a = d1[N][j]-d1[i][j] # 1
        b = N-a-i # 0

        if n%2:
            ans += b*(2**j)
        else:
            ans += a*(2**j)
        n//=2
	ans %= mod

print(ans)

Buggy submission (verdict: Runtime Error):
import numpy as np
N = int(input())
*A, = map(int, input().split())

d1 = np.ndarray([[0]*60 for _ in range(N+1)])
mod = 10**9+7

for i, n in enumerate(A, start=1):
    for j in range(60):
        d1[i][j] = d1[i-1][j]
        if n%2:
            d1[i][j] += 1
        n//=2

ans = 0
for i, n in enumerate(A, start=1):
    for j in range(60):
        a = d1[N][j]-d1[i][j] # 1
        b = N-a-i # 0

        if n%2:
            ans += b*(2**j)
        else:
            ans += a*(2**j)
        ans %= mod
        n//=2

print(ans)
Problem p02853 (python)

Fixed submission:
from collections import defaultdict
X, Y = map(int, input().split())
d = defaultdict(int)
d[1] = 300000
d[2] = 200000
d[3] = 100000
ans = d[X]+d[Y]
if X==1 and Y==1:
  ans += 400000
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
X, Y = map(int, input().split())
d = defaultdict(int)
d[1] = 300000
d[2] = 200000
d[3] = 100000
ans = d[X]+d[Y]
if X==1 and Y==1:
  ans += 400000
print(ans

Buggy submission (verdict: Runtime Error):
X, Y = map(int, input().split())
d = {1:300000, 2:200000, 3:100000}
ans = d[X]+d[Y]
if X==1 and Y==1:
  ans += 400000
print(ans)

Buggy submission (verdict: Runtime Error):
X, Y = map(int, input().split())
d = {1:300000, 2:200000, 3:100000}
ans = d[X]+d[Y]
if X==1 and Y==1:
  ans += 400000
print(ans
Problem p02889 (python)

Fixed submission:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())
inf = 10**15
V = [[] for _ in range(N)]

for _ in range(M):
    A, B, C = map(int, input().split())
    if C>L:continue
    V[A-1].append((B-1, C))
    V[B-1].append((A-1, C))

dists = []
for i in range(N):
    dist = [(inf,inf)] * N
    dist[i] = (0, 0)
    u = [False] * N
    for _ in range(N):
        (charged, used), j = min([(dist[i], i) for i in range(N) if not u[i]])
        u[j] = True
        for k, next_cost in V[j]:
            if j==k: continue
            c = (charged+1, next_cost) if used+next_cost>L else (charged, used+next_cost)
            if dist[k] > c:
                dist[k] = c
    dists.append(dist)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = dists[s-1][t-1][0]
    print(ans if ans!=inf else -1)

Buggy submission (verdict: Runtime Error):
from heapq import heappush, heappop
input = sys.stdin.readline

N, M, L = map(int, input().split())
inf = 10**20
d = [[inf]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i==j:
            d[i][j] = 0

for _ in range(M):
    A, B, C = map(int, input().split())
    d[A-1][B-1] = C
    d[B-1][A-1] = C

charged_dict = [[(inf,inf)]*N for _ in range(N)]
for j in range(N):
    charged_dict[j][j] = (0, 0)
    q = [(0, -L, j)]
    while q:
        charged, fuel, u = heappop(q)
        for v, next_cost in enumerate(d[u]):
            if next_cost == inf:
                continue
            c = (charged+1, -(L-next_cost)) if -fuel-next_cost<0 else (charged, -(-fuel-next_cost))
            if charged_dict[j][v] > c:
                charged_dict[j][v] = c
                heappush(q, c+(v,))

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = charged_dict[s-1][t-1][0]
    print(ans if ans!=inf else -1)
Problem p02903 (python)

Fixed submission:
H, W, A, B = map(int, input().split())
l = [[0]*W for _ in range(H)]

for i in range(B):
    for j in range(A):
        l[i][j] = 1

for i in range(B, H):
    for j in range(A, W):
        l[i][j] = 1

for i in l:
    print("".join(map(str, i)))

Buggy submission (verdict: Runtime Error):
H, W, A, B = map(int, input().split())
if H==1:
    print("".join(map(str,[1]*A+[0]*(W-A))))
elif W==1:
    for i in [1]*B+[0]*(H-B):
        print(i)
elif W%A==0 and H%B==0 and A*(H//B)==W:
    a, b = 0, 0
    l = [[0]*W for _ in range(H)]
    
    while B*b<H and A*a<W:
        for i in range(B):
            for j in range(A):
                l[B*b+i][A*a+j] = 1
        a += 1
        b += 1
    for i in l:
        print("".join(map(str,i)))
else:
    print("No")

Buggy submission (verdict: Runtime Error):
H, W, A, B = map(int, input().split())
if H==1:
    print("".join(map(str,[1]*A+[0]*(W-A))))
elif W==1:
    for i in [1]*B+[0]*(H-B):
        print(i)
elif W%A==0 and H%B==0 and A*(H//B)==W:
    a, b = 0, 0
    l = [[0]*W for _ in range(H)]
    while B*b<H and A*a<W:
        for i in range(A):
            for j in range(B):
                l[A*a+i][B*b+j] = 1
        a += 1
        b += 1
    for i in l:
        print("".join(map(str,i)))
else:
    print("No")

Buggy submission (verdict: Runtime Error):
H, W, A, B = map(int, input().split())
if H==1:
    print("".join(map(str,[1]*A+[0]*(W-A))))
elif W==1:
    for i in [1]*B+[0]*(H-B):
        print(i)
elif W%A==0 and H%B==0:
    a, b = 0, 0
    l = [[0]*W for _ in range(H)]
    while B*b<H and A*a<W:
        for i in range(A):
            for j in range(B):
                l[A*a+i][B*b+j] = 1
        a += 1
        b += 1
    for i in l:
        print("".join(map(str,i)))
else:
    print("No")

Buggy submission (verdict: Runtime Error):
H, W, A, B = map(int, input().split())
if H==1:
    print("".join(map(str,[1]*A+[0]*(W-A))))
elif W==1:
    for i in [1]*B+[0]*(H-B):
        print(i)
elif W%A==0 and H%B==0:
    a, b = 0, 0
    l = [[0]*W for _ in range(H)]
    while B*b<H and A*a<W:
        for i in range(A):
            for j in range(B):
                l[a+i][b+j] = 1
        a += 1
        b += 1
    for i in l:
        print("".join(map(str,i)))
else:
    print("No")
Problem p02904 (python)

Fixed submission:
from operator import add


class SegTree():
    def __init__(self, N, e, operator_func=add):
        self.e = e # 単位元
        self.size = N
        self.node = [self.e] * (2*N)
        self.operator_func = operator_func # 処理(add or xor max minなど)

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.operator_func(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size-1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.operator_func(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        # [l, r) についてqueryを求める
        x = self.e
        l += self.size
        r += self.size

        while l<r:
            if l&1:
                x = self.operator_func(x, self.node[l-1])
                l += 1
            if r&1:
                r -= 1
                x = self.operator_func(x, self.node[r-1])
            l >>= 1
            r >>= 1
        return x


N, K = map(int, input().split())
*P, = map(int, input().split())
INF = 10**12

tree_max = SegTree(N, -INF, operator_func=max)
tree_max.set_list(P)
tree_min = SegTree(N, INF, operator_func=min)
tree_min.set_list(P)
tree_monoinc = SegTree(N, INF, operator_func=min)
for i in range(N):
    tree_monoinc.update(i, P[i]-P[i-1] if i else 0)

def isMonoinc(l, r):
    # [l, r)
    l += 1
    return tree_monoinc.get(l, r)>=0

ans = N-K+1
orig = 0

for i in range(N-K+1):
    if isMonoinc(i, i+K):
        orig = 1
        ans -= 1
    elif i+K<N and tree_max.get(i, i+K+1)==P[i+K] and tree_min.get(i, i+K+1)==P[i]:
        ans -= 1

ans += orig
print(ans)

Buggy submission (verdict: Runtime Error):
T1, T2 = map(int, input().split())
A1, A2 = map(int, input().split())
B1, B2 = map(int, input().split())

d1 = T1*(A1-B1)
d2 = T2*(A2-B2)
if d1>d2:
    d1 *= -1
    d2 *= -1

if (d1>0 and d1+d2>0) or (d1<0 and d1+d2<0):
    print(0)
elif d1+d2==0:
    print("infinity")
else:
    v = (abs(d1)//(d1+d2))
    ans = v*2
    pos = d1+v*(d1+d2)
    if pos<0 and pos+d2>=0:
        ans += 1
    print(pos)
Problem p02913 (python)

Fixed submission:
N = int(input())
S = input()
dp = [[0]*(N+1) for _ in range(N+1)]

for l in range(N)[::-1]:
    for r in range(l+1, N)[::-1]:
        dp[l][r] = dp[l+1][r+1]+1 if S[l]==S[r] else 0

ans = 0 
for l in range(N)[::-1]:
    for r in range(l+1, N)[::-1]:
        ans = max(ans, min(r-l, dp[l][r]))
print(ans)

Buggy submission (verdict: Runtime Error):
class RollingHash:
    def __init__(self, s):
        b1, b2 = 1007, 2009
        self.mod1, self.mod2 = 10**9+7, 10**9+9
        self.size = len(s)
        self.string = s

        self.hash1 = self.make_hashtable(b1, mod1)
        self.hash2 = self.make_hashtable(b2, mod2)
        self.pow1 = self.make_powtable(b1, mod1)
        self.pow2 = self.make_powtable(b2, mod2)

    def make_hashtable(self, B, MOD):
        hashtable = [0] * (self.size+1)
        for i in range(1, self.size+1):
            hashtable[i] = (hashtable[i-1] * B + ord(self.string[i-1]))%MOD
        return hashtable
    
    def make_powtable(self, B, MOD):
        power = [0] * (self.size+1)
        power[0] = 1
        for i in range(1, self.size+1):
            power[i] = (B * power[i-1])%MOD
        return power

    def get_hash(self, l, length):
        r = length+l-1
        l -= 1
        h1 = (self.hash1[r]-self.hash1[l]*self.pow1[r-l])%self.mod1
        h2 = (self.hash2[r]-self.hash2[l]*self.pow2[r-l])%self.mod2
        return (h1, h2)

from collections import defaultdict

def solve1():
    N = int(input())
    S = input()
    size = len(S)
    hash_table = RollingHash(S)

    ans = 0
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if S[i-1]!=S[j-1]:continue

            left = 1
            right = min(j-i, size-j+1)+1

            while right-left>1:
                m = (left+right)//2
                if hash_table.get_hash(i, m)==hash_table.get_hash(j, m):
                    left = m
                else:
                    right = m
            ans = max(ans, left)

    print(ans)


def solve2():
    N = int(input())
    S = input()
    size = len(S)
    hash_table = RollingHash(S)

    def check(m):
        d = defaultdict(lambda :10**20)
        for i in range(1, size-m+2):
            h = hash_table.get_hash(i, m)
            d[h] = min(d[h], i)
            if (i-d[h])>=m:
                return True
        return False

    left, right = 0, size//2 + 1
    while right-left>1:
        m = (right+left)//2
        if check(m):
            left = m
        else:
            right = m

    print(left)

if __name__ == "__main__":
    # solve1()
    solve2()