Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

G = defaultdict(list)

N = int(input())
C = [0 for i in range(N)]
last = N


def rec(pos, c):
    """ 2 色で塗ることができることが保証されている """
    global C
    C[pos] = c
    for to in G[pos]:
        if C[to] == 0:
            rec(to, -c)


for i in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1; v -= 1
    # 無向グラフ
    if w%2 == 0:
        G[u].append(last)
        G[last].append(u)
        G[v].append(last)
        G[last].append(v)
        C.append(0)
        last += 1
    else:
        G[u].append(v)
        G[v].append(u)
rec(0, 1)
for i in range(N):
    print(0 if C[i] == -1 else 1)

Fixed submission:
from collections import defaultdict
import sys

sys.setrecursionlimit(1000000)

G = defaultdict(list)

N = int(input())
C = [0 for i in range(N)]
last = N


def rec(pos, c):
    """ 2 色で塗ることができることが保証されている """
    global C
    C[pos] = c
    for to in G[pos]:
        if C[to] == 0:
            rec(to, -c)


for i in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1; v -= 1
    # 無向グラフ
    if w%2 == 0:
        G[u].append(last)
        G[last].append(u)
        G[v].append(last)
        G[last].append(v)
        C.append(0)
        last += 1
    else:
        G[u].append(v)
        G[v].append(u)
rec(0, 1)
for i in range(N):
    print(0 if C[i] == -1 else 1)
Buggy python submission (verdict: Time Limit Exceeded):
def gcd(x, y):
    xx = 0; yy = 0
    if x >= y:
        xx = x; yy = y
    else:
        xx = y; yy = x
    while yy > 0:
        xx, yy = yy, xx%yy
    return xx


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    ans = 1
    for i in range(n):
        tmp = -1
        for j in range(n):
            if j == i:
                continue
            if tmp == -1:
                tmp = a[j]
            tmp = gcd(tmp, a[j])
        ans = max(ans, tmp)
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
def gcd(x, y):
    xx = 0; yy = 0
    if x >= y:
        xx = x; yy = y
    else:
        xx = y; yy = x
    while yy > 0:
        xx, yy = yy, xx%yy
    return xx


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    # i を入れた場合のgcdと i を入れない場合のgcdを考える
    ans = 1
    # gcd の結合則を利用する(X, Y, Zがありgcd(gcd(x,y),z)==gcd(x,gcd(x, y)))
    l = [0 for i in range(n)]
    r = [0 for i in range(n+1)]
    for i in range(n-1):
        l[i+1] = gcd(l[i], a[i])
    for i in range(n-1, -1, -1):
        r[i] = gcd(r[i+1],a[i])
    for i in range(n):
        ans = max(ans, gcd(l[i], r[i+1]))
    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
from math import gcd

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    ans = 1
    for i in range(n):
        tmp = -1
        for j in range(n):
            if j == i:
                continue
            if tmp == -1:
                tmp = a[j]
            tmp = gcd(tmp, a[j])
        ans = max(ans, tmp)
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
def gcd(x, y):
    xx = 0; yy = 0
    if x >= y:
        xx = x; yy = y
    else:
        xx = y; yy = x
    while yy > 0:
        xx, yy = yy, xx%yy
    return xx


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    # i を入れた場合のgcdと i を入れない場合のgcdを考える
    ans = 1
    # gcd の結合則を利用する(X, Y, Zがありgcd(gcd(x,y),z)==gcd(x,gcd(x, y)))
    l = [0 for i in range(n)]
    r = [0 for i in range(n+1)]
    for i in range(n-1):
        l[i+1] = gcd(l[i], a[i])
    for i in range(n-1, -1, -1):
        r[i] = gcd(r[i+1],a[i])
    for i in range(n):
        ans = max(ans, gcd(l[i], r[i+1]))
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
from collections import Counter


def main():
    s = input()
    k = int(input())
    substr = []
    for l in range(len(s)):
        for r in range(l+1,len(s)+1):
            substr.append(s[l:r])
    c = Counter(substr)
    c = sorted(c.keys())
    print(c[k-1])


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    s = input()
    k = int(input())
    substr = []
    for l in range(len(s)):
        for r in range(l+1,len(s)+1):
            if r-l > k:
                break
            substr.append(s[l:r])
    c=sorted(set(substr))

    print(c[k-1])


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):


def binsearch(x,value):
    left=0; right=len(x)-1
    if x[right] == value:
        return right
    elif x[left] == value:
        return left
    while True:
        m = (right+left)//2
        if x[m] == value:
            return m
        elif x[m] > value:
            right = m
        else:
            left = m


def main():
    n = int(input())
    x = [int(i) for i in input().split()]
    newx = sorted(x)
    for i in x:
        index = binsearch(newx,i)
        del newx[index]
        print(newx[(n-1)//2])
        newx.insert(index,i)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    n = int(input())
    x = [int(i) for i in input().split()]
    newx = sorted(x)
    ans = dict()
    for i,xx in enumerate(newx):
        if i+1 <= n//2:
            ans[xx] = newx[n//2]
        else:
            ans[xx] = newx[n//2-1]
    for xx in x:
        print(ans[xx])

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    x = [int(i) for i in input().split()]
    for i in range(len(x)):
        tmp = x[i]
        del x[i]
        newx = sorted(x)
        print(newx[len(newx)//2])
        x.insert(i, tmp)

if __name__ == '__main__':
    main()

Fixed submission:
def main():
    n = int(input())
    x = [int(i) for i in input().split()]
    newx = sorted(x)
    ans = dict()
    for i,xx in enumerate(newx):
        if i+1 <= n//2:
            ans[xx] = newx[n//2]
        else:
            ans[xx] = newx[n//2-1]
    for xx in x:
        print(ans[xx])

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from math import factorial as fact
from itertools import combinations as comb


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    ans = [0,0]
    tmp = 0
    for i,j in comb(a,2):
        t = fact(max(i,j))//(fact(max(i,j)-min(i,j))*fact(min(i,j)))
        if tmp < t:
            ans = [max(i,j),min(i,j)]
            tmp = t
    print(ans[0],ans[1])


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    ma = max(a)
    diff = 100000000000000
    ans = 0
    for aa in a:
        t = abs(ma//2-aa)
        if ma != aa and diff > t:
            diff = t
            ans = aa
    print(ma,ans)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
	n, a, b = [int(i) for i in input().split()]
    ans = 0
    for i in range(1,n+1):
        tmp = 0
        for ss in str(i):
            tmp += int(ss)
        if a <= tmp <= b:
            ans += tmp
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    n, a, b = [int(i) for i in input().split()]
    ans = 0
    for i in range(1,n+1):
        tmp = 0
        for ss in str(i):
            tmp += int(ss)
        if a <= tmp <= b:
            ans += i
    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
def main():
    n = int(input())
    a = int(input())
    b = int(input())
    ans = 0
    for i in range(1,n+1):
        tmp = 0
        for ss in str(i):
            tmp += int(ss)
        if a <= tmp <= b:
            ans += tmp
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    n, a, b = [int(i) for i in input().split()]
    ans = 0
    for i in range(1,n+1):
        tmp = 0
        for ss in str(i):
            tmp += int(ss)
        if a <= tmp <= b:
            ans += i
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

G = defaultdict(list)


N, M = map(int, input().split())
visited = [[False for i in range(N)] for j in range(5)]
for i in range(M):
    v,u = map(int, input().split())
    G[v-1].append(u-1)
    G[u-1].append(v-1)

# 頂点間に奇数長のパスがあるかどうか確認するために 2部グラフ 判定をする
COLOR = [0 for i in range(N)]

def dfs(pos, color):
    global COLOR
    COLOR[pos] = color
    ans = True
    for to in G[pos]:
        if COLOR[to] == color:
            return False
        elif COLOR[to] == 0:
            ans &= dfs(to, -color)
    return ans

if dfs(0, 1):
    count = 0
    for i in COLOR:
        if i == -1:
            count += 1
    another = N-count
    print(count*another-M)
else:
    # 2 部グラフではなかったので、完全グラフから M を引いた値を出力する
    print(N*(N-1)//2-M)


Fixed submission:
import sys

sys.setrecursionlimit(100000)
from collections import defaultdict

G = defaultdict(list)


N, M = map(int, input().split())
visited = [[False for i in range(N)] for j in range(5)]
for i in range(M):
    v,u = map(int, input().split())
    G[v-1].append(u-1)
    G[u-1].append(v-1)

# 頂点間に奇数長のパスがあるかどうか確認するために 2部グラフ 判定をする
COLOR = [0 for i in range(N)]

def dfs(pos, color):
    global COLOR
    COLOR[pos] = color
    ans = True
    for to in G[pos]:
        if COLOR[to] == color:
            return False
        elif COLOR[to] == 0:
            ans &= dfs(to, -color)
    return ans

if dfs(0, 1):
    count = 0
    for i in COLOR:
        if i == -1:
            count += 1
    another = N-count
    print(count*another-M)
else:
    # 2 部グラフではなかったので、完全グラフから M を引いた値を出力する
    print(N*(N-1)//2-M)
Buggy python submission (verdict: Time Limit Exceeded):
n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]

for i in range(1, n+1):
    tmp = a.count(i)
    if k+tmp-q > 0:
        print("Yes")
    else:
        print("No")

Fixed submission:
from collections import defaultdict
n, k, q = map(int, input().split())
d = defaultdict(int)
for i in range(q):
    tmp = int(input())
    d[tmp] += 1

for i in range(1, n+1):
    if k+d[i]-q > 0:
        print("Yes")
    else:
        print("No")
Buggy python submission (verdict: Runtime Error):
n = int(input())
t = n
c = 0
while t > 0:
    t //= 10
    c += 1
ans = 0
for i in range(1, c+1, 2):
    if i == c:
        tmp = int(str(n)[1:])
        ans += (tmp + 1)
    else:
        ans += (10**i - 10**(i-1))
print(ans)

Fixed submission:
n = int(input())
t = n
c = 0
while t > 0:
    t //= 10
    c += 1
ans = 0
for i in range(1, c+1, 2):
    if i == c:
        ans += n - 10 ** (i-1) + 1
    else:
        ans += (10**i - 10**(i-1))
print(ans)
Buggy python submission (verdict: Runtime Error):
n, x = map(int, input().split())
l = list(map(int, input().split()))

ans = 0
d = 0
while(d <= x):
    d = d + l[ans]
    ans += 1
print(ans)

Fixed submission:
n, x = map(int, input().split())
l = list(map(int, input().split()))

ans = 0
d = 0
while(d <= x):
    if ans == n:
        ans += 1
        break
    d = d + l[ans]
    ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

from operator import itemgetter
n, m = map(int, input().split())
a = list(map(int, input().split()))
l = [list(map(int, input().split())) for _ in range(m)]
l = sorted(l, key=itemgetter(1), reverse=True)
a = sorted(a)
idx = 0
for b, c in l:
    cnt = 1
    while(cnt <= b):
        if a[idx] < c:
            a[idx] = c
            idx += 1
            cnt += 1
        else:
            break
print(sum(a))
        


Fixed submission:
import sys
input = sys.stdin.readline
from operator import itemgetter
n, m = map(int, input().split())
a = list(map(int, input().split()))
l = [list(map(int, input().split())) for _ in range(m)]
l = sorted(l, key=itemgetter(1), reverse=True)
a = sorted(a)
idx = 0
cont_flag = 1
for b, c in l:
    cnt = 1
    while(cnt <= b and cont_flag):
        if a[idx] < c:
            a[idx] = c
            idx += 1
            cnt += 1
            if idx == n:
                cont_flag = 0
        else:
            break
    if not cont_flag:
        break
print(sum(a))
Buggy python submission (verdict: Time Limit Exceeded):
r, g, b, n = map(int, input().split())
ans = 0

l = [r, g, b]
l.sort(reverse=True)
for i in range(n+1):
    if l[0]*i > n:
        break
    for j in range(n+1):
        if l[0]*i + l[1]*j > n:
            break
        elif (n-(l[0]*i + l[1]*j)) % l[2] == 0:
            ans += 1
print(ans)

Fixed submission:
r, g, b, n = map(int, input().split())
ans = 0

l = [r, g, b]
l.sort(reverse=True)
a = n // l[0]
for i in range(a+1):
    for j in range(n+1):
        if l[0]*i + l[1]*j > n:
            break
        elif (n-(l[0]*i + l[1]*j)) % l[2] == 0:
            ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd
n = int(input())
A = list(map(int, input().split()))

def gcd_list(l):
    if len(l) == 0:
        l.append(0)
    res = l[0]
    for i in range(len(l)):
        res = gcd(res, l[i])
    return res

m = []
left = 0
for i in range(n):
    if i == 0:
        left = 0
    else:
        left = gcd(left, A[i-1])
        
    right = gcd_list(A[i+1:])
    m.append(gcd(left, right))

print(max(m))

Fixed submission:
from fractions import gcd
n = int(input())
A = list(map(int, input().split()))

m = []
left = [0]
right = [0]
for i in range(n):
    left.append(gcd(left[i], A[i]))
    right.append(gcd(right[i], A[n-i-1]))
    

for i in range(n):
    m.append(gcd(left[i], right[n-i-1]))
    
print(max(m))

Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd
n = int(input())
A = list(map(int, input().split()))

def gcd_list(l):
    if len(l) == 0:
        l.append(0)
    res = l[0]
    for i in range(len(l)):
        res = gcd(res, l[i])
    return res

m = []
for i in range(n):
    left = gcd_list(A[:i])
    if i == n-1:
        right = 0
    else:
        right = gcd_list(A[i+1:])
    m.append(gcd(left, right))

print(max(m))

Fixed submission:
from fractions import gcd
n = int(input())
A = list(map(int, input().split()))

m = []
left = [0]
right = [0]
for i in range(n):
    left.append(gcd(left[i], A[i]))
    right.append(gcd(right[i], A[n-i-1]))
    

for i in range(n):
    m.append(gcd(left[i], right[n-i-1]))
    
print(max(m))
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

n = int(input())
s = input()

left = 0
right = s.count(".")
res = min(right, s.count("#"))
for i in range(n):
    if s[i] == "#":
        left += 1
    else:
        right -= 1
    res = min(res, left+right)

print(res)

Fixed submission:
a, b, c = map(int, input().split())
if a < c and b > c:
    print("Yes")
elif b < c and a > c:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
S = input()
lr = [list(map(int, input().split())) for _ in range(Q)]

for l, r in lr:
    sub = S[l-1:r]
    dp = [0 for _ in range(len(sub))]
    for i in range(len(dp)):
        if sub[i:i+2] == "AC":
            dp[i] = 1
    print(sum(dp))

Fixed submission:
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
S = input()
lr = [list(map(int, input().split())) for _ in range(Q)]

ac = [0] * N
cnt = 0
for i in range(1, N):
    if S[i-1:i+1] == "AC":
        cnt += 1
    ac[i] = cnt
    
for l, r in lr:
    print(ac[r-1] - ac[l-1])
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
count = 0
while True:
    flag = []
    S = list(S)
    for i in range(len(S)):
        if i == 0:
            pre_s = S[i]
            flag.append(0)
        else:
            if pre_s != S[i] and flag[i-1] == 0:
                flag.append(1)
                flag[i-1] = 1
                pre_s = S[i]
                S[i-1] = "a"
                S[i] = "a"
            else:
                flag.append(0)
                pre_s = S[i]
            
    if sum(flag) == 0:
        break
    else:
        count += sum(flag)

    S = "".join(S).replace("a", "")
            
print(count)

Fixed submission:
S = input()
a = S.count("0")
b = S.count("1")
if a<b:
    print(a*2)
else:
    print(b*2)

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
count = 0
while True:
    flag = []
    for i in range(len(S)):
        if i == 0:
            pre_s = S[i]
            flag.append(0)
        else:
            if pre_s != S[i] and flag[i-1] == 0:
                flag.append(1)
                flag[i-1] = 1
                pre_s = S[i]
            else:
                flag.append(0)
                pre_s = S[i]
            
    if sum(flag) == 0:
        break
    else:
        count += sum(flag)

    S = list(S)
    for i in range(len(flag)):
        if flag[i]:
            S[i] = "a"
    S = "".join(S).replace("a", "")
            
print(count)

Fixed submission:
S = input()
a = S.count("0")
b = S.count("1")
if a<b:
    print(a*2)
else:
    print(b*2)
Buggy python submission (verdict: Runtime Error):
import sys
from math import gcd
input = sys.stdin.readline

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

f = A[0]
for i in range(1, N):
    f = gcd(f, A[i])
print(f)

Fixed submission:
import sys
from fractions import gcd
input = sys.stdin.readline

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

f = A[0]
for i in range(1, N):
    f = gcd(f, A[i])
print(f)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

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

living = N
while(living > 1):
    A = sorted(A)
    if A[N-1] % A[N-2] == 0:
        living -= 1
    A[N-1] = A[N-1] % A[N-2]
    
print(sum(A))


Fixed submission:
import sys
from fractions import gcd
input = sys.stdin.readline

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

f = A[0]
for i in range(1, N):
    f = gcd(f, A[i])
print(f)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]

result = None
for i in range(101):
    for j in range(101):
        judge = True
        x, y, h = l[0]
        highest = abs(i - x) + abs(j - y) + h
        if len(l) == 1:
            result = (x, y, h)
            break
        for x, y, h in l[1:]:
            if abs(i - x) + abs(j - y) + h != highest:
                judge = False
                break
        if judge:
            result = (i, j, highest)
            break
    if result:
        break

print(result[0], result[1], result[2])

Fixed submission:
import sys
input = sys.stdin.readline

n = int(input())
l = []
for _ in range(n):
    x, y, h = map(int, input().split())
    if h >= 1:
        l.append([x, y, h])

result = None
for i in range(101):
    for j in range(101):
        judge = True
        x, y, h = l[0]
        highest = abs(i - x) + abs(j - y) + h
        if len(l) == 1:
            result = (x, y, h)
            break
        for x, y, h in l[1:]:
            if abs(i - x) + abs(j - y) + h != highest:
                judge = False
                break
        if judge:
            result = (i, j, highest)
            break
    if result:
        break

print(result[0], result[1], result[2])

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]

result = None
for i in range(101):
    for j in range(101):
        judge = True
        x, y, h = l[0]
        highest = abs(i - x) + abs(j - y) + h
        for x, y, h in l[1:]:
            if abs(i - x) + abs(j - y) + h != highest:
                judge = False
                break
        if judge:
            result = (i, j, highest)
            break
    if result:
        break

print(result[0], result[1], result[2])

Fixed submission:
import sys
input = sys.stdin.readline

n = int(input())
l = []
for _ in range(n):
    x, y, h = map(int, input().split())
    if h >= 1:
        l.append([x, y, h])

result = None
for i in range(101):
    for j in range(101):
        judge = True
        x, y, h = l[0]
        highest = abs(i - x) + abs(j - y) + h
        if len(l) == 1:
            result = (x, y, h)
            break
        for x, y, h in l[1:]:
            if abs(i - x) + abs(j - y) + h != highest:
                judge = False
                break
        if judge:
            result = (i, j, highest)
            break
    if result:
        break

print(result[0], result[1], result[2])
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
import sys
input = sys.stdin.readline

s = input()
t = input()
ds = defaultdict(int)
ss = ""
dt = defaultdict(int)
st = ""
a = "abcdefghijklmnopqrstuvwxyz"
s_res = ""
t_res = ""

for i in range(len(s)):
    ds[s[i]] += 1
    dt[t[i]] += 1
    if ds[s[i]] == 1:
        ss += s[i]
    if dt[t[i]] == 1:
        st += t[i]
    s_res += a[ss.find(s[i])]
    t_res += a[st.find(t[i])]
    

if s_res == t_res:
    print("Yes")
else:
    print("No")

Fixed submission:
from collections import defaultdict
import sys
input = sys.stdin.readline

s = input()
t = input()
ds = defaultdict(str)
dt = defaultdict(str)

ans = "Yes"
for c1, c2 in zip(s, t):
    if c1 not in ds:
        ds[c1] = c2
    else:
        if ds[c1] != c2:
            ans = "No"
    
    if c2 not in dt:
        dt[c2] = c1
    else:
        if dt[c2] != c1:
            ans = "No"
print(ans)

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
import sys
input = sys.stdin.readline

s = input()
t = input()
ds = defaultdict(int)
dt = defaultdict(int)
a = "abcdefghijklmnopqrstuvwxyz"
s_res = ""
t_res = ""

for i in range(len(s)):
    ds[s[i]] += 1
    dt[t[i]] += 1
    s_res += a[len(ds)-1]
    t_res += a[len(dt)-1]

if s_res == t_res:
    print("Yes")
else:
    print("No")

Fixed submission:
from collections import defaultdict
import sys
input = sys.stdin.readline

s = input()
t = input()
ds = defaultdict(str)
dt = defaultdict(str)

ans = "Yes"
for c1, c2 in zip(s, t):
    if c1 not in ds:
        ds[c1] = c2
    else:
        if ds[c1] != c2:
            ans = "No"
    
    if c2 not in dt:
        dt[c2] = c1
    else:
        if dt[c2] != c1:
            ans = "No"
print(ans)