Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

def merge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = [None]*(n1+1)
    R = [None]*(n2+1)
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
    L[n1] = float('inf')
    R[n2] = float('inf')
    i = 0
    j = 0
    for k in range(left, right):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
    
if __name__ == '__main__':

    n = int(input())
    S = [int(s) for s in input().split(" ")]
    cnt = 0

    mergeSort(S, 0, n)

    print(" ".join(map(str, S)))
    print(cnt)


Fixed submission:
# -*- coding: utf-8 -*-

def merge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = A[left:left+n1]
    R = A[mid:mid+n2]
    L.append(float('inf'))
    R.append(float('inf'))
    
    i = 0
    j = 0
    for k in range(left, right):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
    
if __name__ == '__main__':

    n = int(input())
    S = [int(s) for s in input().split(" ")]
    cnt = 0

    mergeSort(S, 0, n)

    print(" ".join(map(str, S)))
    print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-


def CountingSort(A, k, n):
    B = [None]*(n+1)
    C = [A.count(i) for i in range(k)]
    for i in range(1, k):
        C[i] = C[i] + C[i-1]
    
    for j in range(n, 0, -1):
        B[C[A[j]]] = A[j]
        C[A[j]] -= 1
    
    return B


if __name__ == '__main__':
    k = 10000
    n = int(input())
    A = [None] + [int(a) for a in input().split(" ")]
    
    B = CountingSort(A, k, n)
    print(" ".join(map(str, B[1:])))



Fixed submission:
# -*- coding: utf-8 -*-


def CountingSort(A, k, n):
    B = [None]*(n+1)
    C = [0]*k
    for j in range(1, n+1):
        C[A[j]] += 1

    for i in range(1, k):
        C[i] = C[i] + C[i-1]
    
    for j in range(n, 0, -1):
        B[C[A[j]]] = A[j]
        C[A[j]] -= 1
    
    return B


if __name__ == '__main__':
    k = 10000
    n = int(input())
    A = [None] + [int(a) for a in input().split(" ")]
    
    B = CountingSort(A, k, n)
    print(" ".join(map(str, B[1:])))

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-


def CountingSort(A, k, n):
    B = [None]*(n+1)
    C = [A.count(i) for i in range(k)]
    for i in range(1, k):
        C[i] = C[i] + C[i-1]
    
    for j in range(n, 0, -1):
        B[C[A[j-1]]] = A[j-1]
        C[A[j-1]] -= 1
    
    return B


if __name__ == '__main__':
    k = 10000
    n = int(input())
    A = [int(a) for a in input().split(" ")]
    

    B = CountingSort(A, k, n)
    print(" ".join(map(str, B[1:])))



Fixed submission:
# -*- coding: utf-8 -*-


def CountingSort(A, k, n):
    B = [None]*(n+1)
    C = [0]*k
    for j in range(1, n+1):
        C[A[j]] += 1

    for i in range(1, k):
        C[i] = C[i] + C[i-1]
    
    for j in range(n, 0, -1):
        B[C[A[j]]] = A[j]
        C[A[j]] -= 1
    
    return B


if __name__ == '__main__':
    k = 10000
    n = int(input())
    A = [None] + [int(a) for a in input().split(" ")]
    
    B = CountingSort(A, k, n)
    print(" ".join(map(str, B[1:])))
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-


if __name__ == '__main__':

    H, W = map(int, input().split())
    C = []
    dp = []
    for i in range(H):
        l = input().split()
        C.append([int(x) for x in l])
        dp.append([(int(x) + 1) % 2 for x in l])

    max_width = 1
    for i in range(1, H):
        for j in range(1, W):
            if C[i][j] == 0:
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1],
                               dp[i - 1][j - 1]) + 1
                max_width = max(max_width, dp[i][j])
    print(max_width**2)
s


Fixed submission:
# -*- coding: utf-8 -*-

from itertools import chain

if __name__ == '__main__':

    H, W = map(int, input().split())
    C = []
    dp = []
    for i in range(H):
        l = input().split()
        C.append([int(x) for x in l])
        dp.append([(int(x) + 1) % 2 for x in l])

    for i in range(1, H):
        for j in range(1, W):
            if C[i][j] == 0:
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1],
                               dp[i - 1][j - 1]) + 1
                
    max_width = max(list(chain.from_iterable(dp)))
    print(max_width**2)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-


if __name__ == '__main__':

    n, m = [int(s) for s in input().split()]
    E = [set() for _ in range(n)]
    for _ in range(m):
        s, t = [int(s) for s in input().split(" ")]
        E[s].add(t)
        E[t].add(s)

    def dfs(current, prev):
        global timer
        prenum[current] = timer
        lowest[current] = prenum[current]
        timer += 1

        visited[current] = 1

        for v in E[current]:
            if visited[v] == 0:
                parent[v] = current
                dfs(v, current)
                lowest[current] = min(lowest[current], lowest[v])
            elif v != prev:  # current -> v is back-edge
                lowest[current] = min(lowest[current], prenum[v])

    prenum = [None] * n
    parent = [None] * n
    lowest = [float("inf")] * n
    timer = 1
    visited = [0] * n

    dfs(0, -1)

    ap = []
    np = 0
    for i in range(1, n):
        p = parent[i]
        if p == 0:
            np += 1
        elif prenum[p] <= lowest[i]:
            ap.append(p)

    if np > 1:
        ap.append(0)

    ap = list(set(ap))
    ap.sort()
    if ap:
        print("\n".join(map(str, ap)))



Fixed submission:
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(200000)


if __name__ == '__main__':

    n, m = [int(s) for s in input().split()]
    E = [set() for _ in range(n)]
    for _ in range(m):
        s, t = [int(s) for s in input().split(" ")]
        E[s].add(t)
        E[t].add(s)

    def dfs(current, prev):
        global timer
        prenum[current] = timer
        lowest[current] = prenum[current]
        timer += 1

        visited[current] = 1

        for v in E[current]:
            if visited[v] == 0:
                parent[v] = current
                dfs(v, current)
                lowest[current] = min(lowest[current], lowest[v])
            elif v != prev:  # current -> v is back-edge
                lowest[current] = min(lowest[current], prenum[v])

    prenum = [None] * n
    parent = [None] * n
    lowest = [float("inf")] * n
    timer = 1
    visited = [0] * n

    dfs(0, -1)

    ap = []
    np = 0
    for i in range(1, n):
        p = parent[i]
        if p == 0:
            np += 1
        elif prenum[p] <= lowest[i]:
            ap.append(p)

    if np > 1:
        ap.append(0)

    ap = list(set(ap))
    ap.sort()
    if ap:
        print("\n".join(map(str, ap)))
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

from collections import deque


if __name__ == '__main__':

    n = int(input())
    A = [[float("inf") for j in range(n)] for i in range(n)]

    for i in range(n - 1):
        A[i][i] = 0
        s, t, d = map(int, input().split())
        A[s][t] = d
        A[t][s] = d

    Q = deque()

    def bfs(s):
        d = [float("inf")] * n
        Q.append(s)
        d[s] = 0
        while Q:
            u = Q.popleft()
            for v in range(n):
                if d[v] == float("inf"):
                    d[v] = d[u] + A[u][v]
                    Q.append(v)

        return d

    d = bfs(0)
    tgt = d.index(max(d))
    d = bfs(tgt)
    print(max(d))



Fixed submission:
# -*- coding: utf-8 -*-

from collections import deque


if __name__ == '__main__':

    n = int(input())
    E = [set() for _ in range(n)]
    for _ in range(n - 1):
        s, t, d = map(int, input().split())
        E[s].add((t, d))
        E[t].add((s, d))

    Q = deque()

    def bfs(s):
        d = [float("inf")] * n
        Q.append(s)
        d[s] = 0
        while Q:
            u = Q.popleft()
            for v, w in E[u]:
                if d[v] == float("inf"):
                    d[v] = d[u] + w
                    Q.append(v)

        return d

    d = bfs(0)
    tgt = d.index(max(d))
    d = bfs(tgt)
    print(max(d))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = list(map(int, input().split()))
Q = int(input())
T = list(map(int, input().split()))
ans = 0
for i in range(Q):
    OK = 0
    NG = N-1
    while abs(OK-NG)>0:
        mid = (OK+NG)//2
        if S[mid]==T[i]:
            ans += 1
            break
        elif S[mid]<T[i]:
            OK = mid
        else:
            NG = mid

print(ans)


Fixed submission:
N = int(input())
S = list(set(map(int, input().split())))
S.sort()
Q = int(input())
T = list(map(int, input().split()))
ans = 0
for i in range(Q):
    OK = 0
    NG = len(S)
    while abs(OK-NG)>1:
        mid = (OK+NG)//2
        if S[mid]<=T[i]:
            OK = mid
        else:
            NG = mid
    if S[OK] == T[i]:
        ans += 1

print(ans)

Buggy python submission (verdict: Runtime Error):
N = int(input())
S = list(set(map(int, input().split())))
S.sort()
Q = int(input())
T = list(map(int, input().split()))
ans = 0
for i in range(Q):
    OK = 0
    NG = N
    while abs(OK-NG)>1:
        mid = (OK+NG)//2
        if S[mid]<=T[i]:
            OK = mid
        else:
            NG = mid
    if S[OK] == T[i]:
        ans += 1

print(ans)


Fixed submission:
N = int(input())
S = list(set(map(int, input().split())))
S.sort()
Q = int(input())
T = list(map(int, input().split()))
ans = 0
for i in range(Q):
    OK = 0
    NG = len(S)
    while abs(OK-NG)>1:
        mid = (OK+NG)//2
        if S[mid]<=T[i]:
            OK = mid
        else:
            NG = mid
    if S[OK] == T[i]:
        ans += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
A = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))

T = pow(2,n)-1

for k in range(q):
    z = 0
    for i in range(T):
        B = list(format(i,"0"+str(n)+"b"))
        sum = 0
        for j in range(n):
            sum += A[j]*int(B[j])
        if sum == m[k]:
            z =1
            break
    if z==1:
        print("yes")
    else:
        print("no")


Fixed submission:
n = int(input())
A = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))


u = set()

def agari(i):
    if X[i]==1:
        X[i]=0
        agari(i+1)
    else:
        X[i]=1

X = [0]*20
k=0
while k<(pow(2,n)-1):
    y = 0
    for l in range(n):
        y += A[l]*X[l]
    u.add(y)
    agari(0)
    k+=1

for j in range(q):
    if m[j] in u:
        print("yes")
    else:
        print("no")

Buggy python submission (verdict: Runtime Error):
n = int(input())
A = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))


def agari(i):
    if X[i]==1:
        X[i]=0
        agari(i+1)
    else:
        X[i]=1

for j in range(q):
    k = 0
    flag = 0
    X = [0] * 10
    while k<(pow(2,n)-1):
        y = 0
        for l in range(n):
            y += A[l]*X[l]
        if y == m[j]:
            flag = 1
            break
        agari(0)
        k+=1
    if flag == 1:
        print("yes")
    else:
        print("no")


Fixed submission:
n = int(input())
A = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))


u = set()

def agari(i):
    if X[i]==1:
        X[i]=0
        agari(i+1)
    else:
        X[i]=1

X = [0]*20
k=0
while k<(pow(2,n)-1):
    y = 0
    for l in range(n):
        y += A[l]*X[l]
    u.add(y)
    agari(0)
    k+=1

for j in range(q):
    if m[j] in u:
        print("yes")
    else:
        print("no")
Buggy python submission (verdict: Time Limit Exceeded):
class Tree:
    def __init__(self):
        self.children = {}
        self.end = False

    def __contains__(self, key):
        if len(key) == 0:
            return self.end

        k, *rest = key
        if k not in self.children:
            return False

        return rest in self.children[k]

    def add(self, key):
        if len(key) > 0:
            k, *rest = key
            if k not in self.children:
                self.children[k] = self.__class__()

            self.children[k].add(rest)
        else:
            self.end = True


class Dictionary:
    def __init__(self):
        self.tree = Tree()

    def insert(self, word):
        self.tree.add(word)

    def find(self, word):
        return word in self.tree


def run():
    count = int(input())
    words = Dictionary()

    for _ in range(count):
        command, v = input().split()

        if command == 'insert':
            words.insert(v)
        elif command == 'find':
            if words.find(v):
                print('yes')
            else:
                print('no')
        else:
            raise ValueError()


if __name__ == '__main__':
    run()



Fixed submission:
import sys 


class Tree:
    def __init__(self):
        self.children = {}
        self.end = False

    def __contains__(self, key):
        if len(key) == 0:
            return self.end

        k, *rest = key 
        if k not in self.children:
            return False

        return rest in self.children[k]

    def add(self, key):
        if len(key) > 0:
            k, *rest = key 
            if k not in self.children:
                self.children[k] = self.__class__()

            self.children[k].add(rest)
        else:
            self.end = True


class Dictionary:
    def __init__(self):
        self.tree = Tree()

    def insert(self, word):
        self.tree.add(word)

    def find(self, word):
        return word in self.tree


def run():
    _ = int(input())  # flake8: noqa
    words = Dictionary()

    for command in sys.stdin:

        if command.startswith('insert'):
            words.insert(command[7:])
        elif command.startswith('find'):
            if words.find(command[5:]):
                print('yes')
            else:
                print('no')
        else:
            raise ValueError()


if __name__ == '__main__':
    run()
Buggy python submission (verdict: Runtime Error):
def merge_sort(alist):
    """Sort alist using mergesort.
    Returns a tuple of the number of comparisons and sorted list.

    >>> merge_sort([8, 5, 9, 2, 6, 3, 7, 1, 10, 4])
    (34, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
    """
    def _sort(left, right):
        count = 0
        if left + 1 < right:
            mid = (left + right) // 2
            count += _sort(left, mid)
            count += _sort(mid, right)
            count += merge(left, mid, right)

        return count

    def merge(left, mid, right):
        count = 0
        ll = alist[left:mid] + [SENTINEL]
        rl = alist[mid:right] + [SENTINEL]

        i = j = 0
        for k in range(left, right):
            count += 1
            if ll[i] <= rl[j]:
                alist[k] = ll[i]
                i += 1
            else:
                alist[k] = rl[j]
                j += 1

        return count

    comp = _sort(0, len(alist))
    return (comp, alist)


def run():
    _ = int(input())  # flake8: noqa

    li = [int(i) for i in input().split()]

    (c, s) = merge_sort(li)
    print(" ".join([str(i) for i in s]))
    print(c)


if __name__ == '__main__':
    run()



Fixed submission:
SENTINEL = 10**9 + 1


def merge_sort(alist):
    """Sort alist using mergesort.
    Returns a tuple of the number of comparisons and sorted list.

    >>> merge_sort([8, 5, 9, 2, 6, 3, 7, 1, 10, 4])
    (34, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
    """
    def _sort(left, right):
        count = 0
        if left + 1 < right:
            mid = (left + right) // 2
            count += _sort(left, mid)
            count += _sort(mid, right)
            count += merge(left, mid, right)

        return count

    def merge(left, mid, right):
        count = 0
        ll = alist[left:mid] + [SENTINEL]
        rl = alist[mid:right] + [SENTINEL]

        i = j = 0
        for k in range(left, right):
            count += 1
            if ll[i] <= rl[j]:
                alist[k] = ll[i]
                i += 1
            else:
                alist[k] = rl[j]
                j += 1

        return count

    comp = _sort(0, len(alist))
    return (comp, alist)


def run():
    _ = int(input())  # flake8: noqa

    li = [int(i) for i in input().split()]

    (c, s) = merge_sort(li)
    print(" ".join([str(i) for i in s]))
    print(c)


if __name__ == '__main__':
    run()
Buggy python submission (verdict: Runtime Error):
import math


def distance(p1, p2):
    """returns the distance between p1 and p2

    >>> d = distance((0, 0), (1, 1))
    >>> print("{:.5f}".format(d))
    1.41421
    """
    (x1, y1) = p1
    (x2, y2) = p2
    return math.sqrt((x2-x1)**2 + (y2-y1)**2)


def run():
    x1, y1, x2, y2 = [int(i) for i in input().split()]

    print("{:.5f}".format(distance((x1, y1), (x2, y2))))


if __name__ == '__main__':
    run()


Fixed submission:
import math


def distance(p1, p2):
    """returns the distance between p1 and p2

    >>> d = distance((0, 0), (1, 1))
    >>> print("{0:.5f}".format(d))
    1.41421
    """
    (x1, y1) = p1
    (x2, y2) = p2
    return math.sqrt((x2-x1)**2 + (y2-y1)**2)


def run():
    x1, y1, x2, y2 = [float(i) for i in input().split()]

    print(distance((x1, y1), (x2, y2)))


if __name__ == '__main__':
    run()

Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3

import math


def distance(p1, p2):
    """returns the distance between p1 and p2

    >>> d = distance((0, 0), (1, 1))
    >>> print("{0:.5f}".format(d))
    1.41421
    """
    (x1, y1) = p1
    (x2, y2) = p2
    return math.sqrt((x2-x1)**2 + (y2-y1)**2)


def run():
    x1, y1, x2, y2 = [int(i) for i in input().split()]

    print("{0:.5f}".format(distance((x1, y1), (x2, y2))))


if __name__ == '__main__':
    run()


Fixed submission:
import math


def distance(p1, p2):
    """returns the distance between p1 and p2

    >>> d = distance((0, 0), (1, 1))
    >>> print("{0:.5f}".format(d))
    1.41421
    """
    (x1, y1) = p1
    (x2, y2) = p2
    return math.sqrt((x2-x1)**2 + (y2-y1)**2)


def run():
    x1, y1, x2, y2 = [float(i) for i in input().split()]

    print(distance((x1, y1), (x2, y2)))


if __name__ == '__main__':
    run()

Buggy python submission (verdict: Runtime Error):
def distance(p1, p2):
    """returns the distance between p1 and p2

    >>> d = distance((0, 0), (1, 1))
    >>> print("{0:.5f}".format(d))
    1.41421
    """
    (x1, y1) = p1
    (x2, y2) = p2
    return math.sqrt((x2-x1)**2 + (y2-y1)**2)


def run():
    x1, y1, x2, y2 = [float(i) for i in input().split()]

    print("{0:.5f}".format(distance((x1, y1), (x2, y2))))


if __name__ == '__main__':
    run()


Fixed submission:
import math


def distance(p1, p2):
    """returns the distance between p1 and p2

    >>> d = distance((0, 0), (1, 1))
    >>> print("{0:.5f}".format(d))
    1.41421
    """
    (x1, y1) = p1
    (x2, y2) = p2
    return math.sqrt((x2-x1)**2 + (y2-y1)**2)


def run():
    x1, y1, x2, y2 = [float(i) for i in input().split()]

    print(distance((x1, y1), (x2, y2)))


if __name__ == '__main__':
    run()
Buggy python submission (verdict: Runtime Error):
def isIncremental(a, b, c): 
    """ 
    a: int
    b: int
    c: int

    returns "Yes" if a < b < c, otherwise "No"

    >>> isIncremental(1, 3, 8)
    'Yes'
    >>> isIncremental(3, 8, 1)
    'No'
    >>> isIncremental(1, 1, 1)
    'No'
    """
    if a >= b:
        return "No"
    elif b >= c:
        return "No"
    else:
        return "Yes"

if __name__ == '__main__':
    ival = input().split(' ')
    print(isIncremental(int(ival[0]), int(ival[1]), int(ival[2]))

Fixed submission:
def isIncremental(a, b, c):
    """
    a: int
    b: int
    c: int

    returns "Yes" if a < b < c, otherwise "No"

    >>> isIncremental(1, 3, 8)
    'Yes'
    >>> isIncremental(3, 8, 1)
    'No'
    >>> isIncremental(1, 1, 1)
    'No'
    """
    if a >= b:
        return "No"
    elif b >= c:
        return "No"
    else:
        return "Yes"

if __name__ == '__main__':
#   import doctest
#   doctest.testmod()

    ival = input().split(' ')
    print(isIncremental(int(ival[0]), int(ival[1]), int(ival[2])))
Buggy python submission (verdict: Time Limit Exceeded):

def run():
    n = int(input())
    li = []
    index = 0

    for _ in range(n):
        command = input()
        if command.startswith('0'):
            val = int(command[2:])
            li.insert(index, val)
        elif command.startswith('1'):
            i = int(command[2:])
            index += i
        elif command.startswith('2'):
            del(li[index])
        else:
            raise ValueError('invalid command')

    for n in li:
        print(n)


if __name__ == '__main__':
    run()



Fixed submission:
class List:
    def __init__(self, value=None):
        self.value = value
        self.next = None
        self.prev = None

    def insert(self, value):
        node = self.__class__(value)
        node.prev, node.next = self.prev, self
        if self.prev is not None:
            self.prev.next = node
        self.prev = node
        return node

    def delete(self):
        p, n = self.prev, self.next
        self.prev, self.next = None, None
        if p is None:
            n.prev = None
        else:
            n.prev, p.next = p, n
        return n

    def move(self, i):
        node = self
        if i > 0:
            for _ in range(i):
                node = node.next
        else:
            for _ in range(-i):
                node = node.prev
        return node

    def __iter__(self):
        return List.ListIterator(self)

    class ListIterator:
        def __init__(self, node):
            while node.prev is not None:
                node = node.prev
            self.node = node

        def __iter__(self):
            return self

        def __next__(self):
            val = self.node.value
            if val is None:
                raise StopIteration
            self.node = self.node.next
            return val


def run():
    n = int(input())
    li = List()

    for _ in range(n):
        command = input()
        if command.startswith('0'):
            li = li.insert(int(command[2:]))
        elif command.startswith('1'):
            li = li.move(int(command[2:]))
        elif command.startswith('2'):
            li = li.delete()
        else:
            raise ValueError('invalid command')

    for v in li:
        print(v)


if __name__ == '__main__':
    run()