Problem p02605 (python)

Fixed submission:
def main():
    def calc(v, w, i, j, ans):
        if v > 0:
            i[0] += 1
        elif v < 0:
            j[0] += 1
        else:
            if w > 0:
                ans[0] = min(ans[0], w)
                i[0] += 1
            else:
                j[0] += 1

    n = int(input())
    inf = 10**10
    ans = [inf]
    u_list, d_list, l_list, r_list = [], [], [], []
    for _ in range(n):
        x, y, d = input().split()
        x, y = int(x), int(y)
        if d == "D":
            d_list.append((x, y))
        elif d == "R":
            r_list.append((x, y))
        elif d == "L":
            l_list.append((x, y))
        else:
            u_list.append((x, y))
    ld, lr, ll, lu = len(d_list), len(r_list), len(l_list), len(u_list)
    # 1→u,d
    u_list.sort(key=lambda x: (x[0], x[1]))
    d_list.sort(key=lambda x: (x[0], x[1]))
    i, j = [0], [0]
    while(i[0] < lu and j[0] < ld):
        x, y = u_list[i[0]]
        p, q = d_list[j[0]]
        v = p-x
        w = (q-y)*5
        calc(v, w, i, j, ans)
    # 2→r,l
    r_list.sort(key=lambda x: (x[1], x[0]))
    l_list.sort(key=lambda x: (x[1], x[0]))
    i, j = [0], [0]
    while(i[0] < lr and j[0] < ll):
        x, y = r_list[i[0]]
        p, q = l_list[j[0]]
        v = q-y
        w = (p-x)*5
        calc(v, w, i, j, ans)
    # 3→u,l
    u_list.sort(key=lambda x: (x[0]-x[1], x[0]))
    l_list.sort(key=lambda x: (x[0]-x[1], x[0]))
    i, j = [0], [0]
    while(i[0] < lu and j[0] < ll):
        x, y = u_list[i[0]]
        p, q = l_list[j[0]]
        v = (p-q)-(x-y)
        w = (p-x)*10
        calc(v, w, i, j, ans)
    # 4→d,l
    d_list.sort(key=lambda x: (x[0]+x[1], x[0]))
    l_list.sort(key=lambda x: (x[0]+x[1], x[0]))
    i, j = [0], [0]
    while(i[0] < ld and j[0] < ll):
        x, y = d_list[i[0]]
        p, q = l_list[j[0]]
        v = (p+q)-(x+y)
        w = (p-x)*10
        calc(v, w, i, j, ans)
    # 5→u,r
    u_list.sort(key=lambda x: (x[0]+x[1], -x[0]))
    r_list.sort(key=lambda x: (x[0]+x[1], -x[0]))
    i, j = [0], [0]
    while(i[0] < lu and j[0] < lr):
        x, y = u_list[i[0]]
        p, q = r_list[j[0]]
        v = (p+q)-(x+y)
        w = (x-p)*10
        calc(v, w, i, j, ans)
    # 6→d,r
    d_list.sort(key=lambda x: (x[0]-x[1], -x[0]))
    r_list.sort(key=lambda x: (x[0]-x[1], -x[0]))
    i, j = [0], [0]
    while(i[0] < ld and j[0] < lr):
        x, y = d_list[i[0]]
        p, q = r_list[j[0]]
        v = (p-q)-(x-y)
        w = (x-p)*10
        calc(v, w, i, j, ans)
    if ans == [inf]:
        print("SAFE")
    else:
        print(ans[0])


main()

Buggy submission (verdict: Runtime Error):
def main():
    def calc(v, w, i, j, ans):
        if v > 0:
            i[0] += 1
        elif v < 0:
            j[0] += 1
        else:
            if w > 0:
                ans[0] = min(ans[0], w)
                i[0] += 1
            else:
                j[0] += 1

    n = int(input())
    inf = 10**10
    ans = [inf]
    u_list, d_list, l_list, r_list = [], [], [], []
    for _ in range(n):
        x, y, d = input().split()
        x, y = int(x), int(y)
        if d == "D":
            d_list.append((x, y))
        elif d == "R":
            r_list.append((x, y))
        elif d == "L":
            l_list.append((x, y))
        else:
            u_list.append((x, y))
    ld, lr, ll, lu = len(d_list), len(r_list), len(l_list), len(u_list)
    # 1→u,d
    u_list.sort()
    d_list.sort()
    i, j = [0], [0]
    while(i[0] < lu and j[0] < ld):
        x, y = u_list[i[0]]
        p, q = d_list[j[0]]
        v = p-x
        w = (q-y)*5
        calc(v, w, i, j, ans)
    # 2→r,l
    r_list.sort(key=lambda x: x[1])
    l_list.sort(key=lambda x: x[1])
    i, j = [0], [0]
    while(i[0] < lr and j[0] < ll):
        x, y = r_list[i[0]]
        p, q = l_list[j[0]]
        v = q-y
        w = (p-x)*5
        calc(v, w, i, j, ans)
    # 3→u,l
    u_list.sort(key=lambda x: x[0]-x[1])
    l_list.sort(key=lambda x: x[0]-x[1])
    i, j = [0], [0]
    while(i[0] < lu and j[0] < ll):
        x, y = u_list[i[0]]
        p, q = l_list[j[0]]
        v = (p-q)-(x-y)
        w = (p-x)*10
        calc(v, w, i, j, ans)
    # 4→d,l
    d_list.sort(key=lambda x: x[0]+x[1])
    l_list.sort(key=lambda x: x[0]+x[1])
    i, j = [0], [0]
    while(i[0] < ld and j[0] < ll):
        x, y = d_list[i[0]]
        p, q = l_list[j[0]]
        v = (p+q)-(x+y)
        w = (p-x)*10
        calc(v, w, i, j, ans)
    # 5→u,r
    u_list.sort(key=lambda x: (x[0]+x[1], -x[0]))
    r_list.sort(key=lambda x: (x[0]+x[1], -x[0]))
    i, j = [0], [0]
    while(i[0] < lu and j[0] < lr):
        x, y = u_list[i[0]]
        p, q = r_list[j[0]]
        v = (p+q)-(x+y)
        w = (x-p)*10
        calc(v, w, i, j, ans)
    # 6→d,r
    d_list.sort(key=lambda x: (x[0]-x[1], -x[0]))
    r_list.sort(key=lambda x: (x[0]-x[1], -x[0]))
    i, j = [0], [0]
    while(i[0] < ld and j[0] < lr):
        x, y = d_list[i[0]]
        p, q = r_list[j[0]]
        v = (p-q)-(x-y)
        w = (x-p)*10
        calc(v, w, i, j, ans)
    if ans == [inf]:
        print(1/0)
    else:
        print(ans[0])


main()

Buggy submission (verdict: Runtime Error):
def main():
    n = int(input())
    xyp = [input().split() for _ in [0]*n]
    for i in range(n):
        xyp[i][0] = int(xyp[i][0])
        xyp[i][1] = int(xyp[i][1])
    inf = 10**10
    ans = inf
    # 1→u,d
    u_list = []
    d_list = []
    for i in range(n):
        if xyp[i][2] == "U":
            u_list.append((xyp[i][0], xyp[i][1]))
        if xyp[i][2] == "D":
            d_list.append((xyp[i][0], xyp[i][1]))
    li, lj = len(u_list), len(d_list)
    u_list.sort()
    d_list.sort()
    i, j = 0, 0
    while(i < li and j < lj):
        if u_list[i][0] < d_list[j][0]:
            i += 1
        elif u_list[i][0] > d_list[j][0]:
            j += 1
        else:
            if u_list[i][1] < d_list[j][1]:
                ans = min(ans, (d_list[j][1] - u_list[i][1])*5)
                i += 1
            else:
                j += 1
    # 2→r,l
    r_list = []
    l_list = []
    for i in range(n):
        if xyp[i][2] == "R":
            r_list.append((xyp[i][0], xyp[i][1]))
        if xyp[i][2] == "L":
            l_list.append((xyp[i][0], xyp[i][1]))
    li, lj = len(r_list), len(l_list)
    r_list.sort()
    l_list.sort()
    i, j = 0, 0
    while(i < li and j < lj):
        if r_list[i][1] < l_list[j][1]:
            i += 1
        elif r_list[i][1] > l_list[j][1]:
            j += 1
        else:
            if r_list[i][0] < l_list[j][0]:
                ans = min(ans, (l_list[j][0] - r_list[i][0])*5)
                i += 1
            else:
                j += 1
    # 3→u,l
    u_list = []
    l_list = []
    for i in range(n):
        if xyp[i][2] == "U":
            u_list.append((xyp[i][0], xyp[i][1]))
        if xyp[i][2] == "L":
            l_list.append((xyp[i][0], xyp[i][1]))
    li, lj = len(u_list), len(l_list)
    u_list.sort(key=lambda x: x[0]-x[1])
    l_list.sort(key=lambda x: x[0]-x[1])
    i, j = 0, 0
    while(i < li and j < lj):
        if u_list[i][0]-u_list[i][1] < l_list[j][0]-l_list[j][1]:
            i += 1
        elif u_list[i][0]-u_list[i][1] > l_list[j][0]-l_list[j][1]:
            j += 1
        else:
            if u_list[i][0] < l_list[j][0]:
                ans = min(ans, (l_list[j][0] - u_list[i][0])*10)
                i += 1
            else:
                j += 1
    # 4→d,l
    d_list = []
    l_list = []
    for i in range(n):
        if xyp[i][2] == "D":
            d_list.append((xyp[i][0], xyp[i][1]))
        if xyp[i][2] == "L":
            l_list.append((xyp[i][0], xyp[i][1]))
    li, lj = len(d_list), len(l_list)
    d_list.sort(key=lambda x: x[0]+x[1])
    l_list.sort(key=lambda x: x[0]+x[1])
    i, j = 0, 0
    while(i < li and j < lj):
        if d_list[i][0]+d_list[i][1] < l_list[j][0]+l_list[j][1]:
            i += 1
        elif d_list[i][0]+d_list[i][1] > l_list[j][0]+l_list[j][1]:
            j += 1
        else:
            if d_list[i][0] < l_list[j][0]:
                ans = min(ans, (l_list[j][0] - d_list[i][0])*10)
                i += 1
            else:
                j += 1
    # 5→u,r
    u_list = []
    r_list = []
    for i in range(n):
        if xyp[i][2] == "U":
            u_list.append((xyp[i][0], xyp[i][1]))
        if xyp[i][2] == "R":
            r_list.append((xyp[i][0], xyp[i][1]))
    li, lj = len(u_list), len(r_list)
    u_list.sort(key=lambda x: (x[0]+x[1], -x[0]))
    r_list.sort(key=lambda x: (x[0]+x[1], -x[0]))
    i, j = 0, 0
    while(i < li and j < lj):
        if u_list[i][0]+u_list[i][1] < r_list[j][0]+r_list[j][1]:
            i += 1
        elif u_list[i][0]+u_list[i][1] > r_list[j][0]+r_list[j][1]:
            j += 1
        else:
            if u_list[i][0] > r_list[j][0]:
                ans = min(ans, (u_list[j][0] - r_list[i][0])*10)
                i += 1
            else:
                j += 1
    # 6→d,r
    d_list = []
    r_list = []
    for i in range(n):
        if xyp[i][2] == "D":
            d_list.append((xyp[i][0], xyp[i][1]))
        if xyp[i][2] == "R":
            r_list.append((xyp[i][0], xyp[i][1]))
    li, lj = len(d_list), len(r_list)
    d_list.sort(key=lambda x: (x[0]-x[1], -x[0]))
    r_list.sort(key=lambda x: (x[0]-x[1], -x[0]))
    i, j = 0, 0
    while(i < li and j < lj):
        if d_list[i][0]-d_list[i][1] < r_list[j][0]-r_list[j][1]:
            i += 1
        elif d_list[i][0]-d_list[i][1] > r_list[j][0]-r_list[j][1]:
            j += 1
        else:
            if d_list[i][0] > r_list[j][0]:
                ans = min(ans, (d_list[j][0] - r_list[i][0])*10)
                i += 1
            else:
                j += 1
    if ans == inf:
        print("SAFE")
    else:
        print(ans)


main()