Problem:


Score: 600 points

Problem Statement

M-kun is a brilliant air traffic controller.

On the display of his radar, there are N airplanes numbered 1, 2, ..., N, all flying at the same altitude.

Each of the airplanes flies at a constant speed of 0.1 per second in a constant direction. The current coordinates of the airplane numbered i are (X_i, Y_i), and the direction of the airplane is as follows:

if U_i is U, it flies in the positive y direction;

if U_i is R, it flies in the positive x direction;

if U_i is D, it flies in the negative y direction;

if U_i is L, it flies in the negative x direction.

To help M-kun in his work, determine whether there is a pair of airplanes that will collide with each other if they keep flying as they are now.

If there is such a pair, find the number of seconds after which the first collision will happen.

We assume that the airplanes are negligibly small so that two airplanes only collide when they reach the same coordinates simultaneously.

Constraints

1 \leq N \leq 200000

0 \leq X_i, Y_i \leq 200000

U_i is U, R, D, or L.

The current positions of the N airplanes, (X_i, Y_i), are all distinct.

N, X_i, and Y_i are integers.

Input

Input is given from Standard Input in the following format:

N
X_1 Y_1 U_1
X_2 Y_2 U_2
X_3 Y_3 U_3
:
X_N Y_N U_N

Output

If there is a pair of airplanes that will collide with each other if they keep flying as they are now, print an integer representing the number of seconds after which the first collision will happen.

If there is no such pair, print SAFE.

Sample Input 1

2
11 1 U
11 47 D

Sample Output 1

230

If the airplanes keep flying as they are now, two airplanes numbered 1 and 2 will reach the coordinates (11, 24) simultaneously and collide.  

Sample Input 2

4
20 30 U
30 20 R
20 10 D
10 20 L

Sample Output 2

SAFE

No pair of airplanes will collide.

Sample Input 3

8
168 224 U
130 175 R
111 198 D
121 188 L
201 116 U
112 121 R
145 239 D
185 107 L

Sample Output 3

100



Sample input:
2
11 1 U
11 47 D


Sample output:
230

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

"""

上下 or 左右　それぞれの組はすぐ求まる．
同じライン上で上むきと下向きをまとめておいて，上向のaに対して，それよりも上にいて最も近い下向きのを探せば良い．
実際にはもっと早くできそうだけど二分探索で十分早いか

右+上　が当たる場合を考える．
u，rがそれぞれ約N個あるとして
uの中で一番左にあるやつ vs r全部
を考えて，uを左から順に見ていく？
微妙．

当たるとはdx=dyのこと
これ，右向きのやつを通る傾き-1の直線上（かつy座標が上の位置）に右向きのものがあれば当たれる．
45度回転させるか
X=x-y
Y=x+y
で反時計45度回転か．

uとrで，Y座標が同じで，rの方がX座標が小さい
dとlで，Y座標が同じで，dの方がX座標が小さい
dとrで，X座標が同じで，rの方がY座標が小さい
uとlで，X座標が同じで，uの方がY座標が小さい

だるすぎる，直線上の点をみよう，y=-x+kとすればx+y=kなので，kで場合わけ
各kでx座標が小さい順に並べておき，
u,rで，rの方がx座標が小さい
d,rで，rの方がx座標が小さい
u,lで，uの方がx座標が小さい
d,lで，dの方がx座標が小さい

"""
def main():
    import bisect
    
    mod=10**9+7
    N=I()
    M=200000 + 3
    inf = 10**10
    
    X=[0]*N
    Y=[0]*N
    U=[0]*N
    for i in range(N):
        xyu=input().split()
        X[i]=int(xyu[0])
        Y[i]=int(xyu[1])
        U[i]=xyu[2]
        
    # 同じ行/列のものを調べる
    
    xu=[[-inf, inf]for _ in range(M)]
    xd=[[-inf, inf]for _ in range(M)]
    yl=[[-inf, inf]for _ in range(M)]
    yr=[[-inf, inf]for _ in range(M)]
    
    for i in range(N):
        x=X[i]
        y=Y[i]
        if U[i] == "U":
            xu[x].append(y)
        elif U[i] == "D":
            xd[x].append(y)
        elif U[i] == "L":
            yl[y].append(x)
        else:
            yr[y].append(x)
    
    for i in range(M):
        xu[i].sort()
        xd[i].sort()
        yl[i].sort()
        yr[i].sort()
     
    ans_d=inf
    
    # uとかdで走査しても良いけど，全ての頂点を走査したいので此の形が楽
    for i in range(N):
        x=X[i]
        y=Y[i]
        u=U[i]
        
        if u=="U":
            num=bisect.bisect_left(xd[x], y)
            ne=xd[x][num]
            diff=ne-y
            ans_d=min(ans_d,diff)
            
        if u=="D":
            num=bisect.bisect_left(xu[x], y)
            pre=xu[x][num-1]
            diff=y-pre
            ans_d=min(ans_d,diff)
            
        if u=="L":
            num=bisect.bisect_left(yr[y], x)
            pre=yr[y][num-1]
            diff=x-pre
            ans_d=min(ans_d,diff)
            
        if u=="R":
            num=bisect.bisect_left(yl[y], x)
            ne=yl[y][num]
            diff=ne-x
            ans_d=min(ans_d,diff)
            
        # print(i,x,y,diff,ans_d)
    
    ################################################################        
    # ここから斜め

    ku=[[-inf, inf]for _ in range(M*2)]
    kd=[[-inf, inf]for _ in range(M*2)]
    kl=[[-inf, inf]for _ in range(M*2)]
    kr=[[-inf, inf]for _ in range(M*2)]    

    for i in range(N):
        x=X[i]
        y=Y[i]
        k=x+y
        if U[i] == "U":
            ku[k].append(x)
        elif U[i] == "D":
            kd[k].append(x)
        elif U[i] == "L":
            kl[k].append(x)
        else:
            kr[k].append(x)
            
    for i in range(M*2):
        ku[i].sort()
        kd[i].sort()
        kl[i].sort()
        kr[i].sort()
       
    """     
    各kでx座標が小さい順に並べておき，
    u,rで，rの方がx座標が小さい
    d,rで，rの方がx座標が小さい
    u,lで，uの方がx座標が小さい
    d,lで，dの方がx座標が小さい
    """
    
    # print("---")    
    
    ans_d2=inf
    # uとかdで走査しても良いけど，全ての頂点を走査したいので此の形が楽
    for i in range(N):
        x=X[i]
        y=Y[i]
        k=x+y
        if U[i] == "U":
            num=bisect.bisect_left(kr[k],x)
            pre=kr[k][num-1]
            diff=x-pre
            ans_d2=min(ans_d2,diff)

            num=bisect.bisect_left(kl[k],x)
            ne=kl[k][num]
            diff=ne-x
            ans_d2=min(ans_d2,diff)
        elif U[i] == "D":
            num=bisect.bisect_left(kr[k],x)
            pre=kr[k][num-1]
            diff=x-pre
            ans_d2=min(ans_d2,diff)

            num=bisect.bisect_left(kl[k],x)
            ne=kl[k][num]
            diff=ne-x
            ans_d2=min(ans_d2,diff)
        
        # print(i,x,y,pre,ne,diff,ans_d2)
            
    
        
    ans = min(ans_d*5, ans_d2*10) # ans_dは向かい合っているので/2
    
    if ans>=10**8:
        print("SAFE")
    else:
        print(ans)
                 
        

main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import io


def main():
    N = int( sys.stdin.readline() )

    XYU_list = []

    for _ in range(N):
        x,y,u = sys.stdin.readline().rstrip().split()
        XYU_list.append( [int(x),int(y),u] )


    diff = float("inf")

    # check(1) rotate 0 degree
    ret = checkSafety_UD(XYU_list)
    diff = min(diff, ret)
    
    ret = checkSafety_UR(XYU_list)
    diff = min(diff, ret)
    
    # check(2) rotate 90 degree
    rotate(XYU_list)

    ret = checkSafety_UR(XYU_list)
    diff = min(diff, ret)

    # check(3) rotate 180 degree
    rotate(XYU_list)

    ret = checkSafety_UD(XYU_list)
    diff = min(diff, ret)
    
    ret = checkSafety_UR(XYU_list)
    diff = min(diff, ret)

    # check(4) rotate 270 degree
    rotate(XYU_list)

    ret = checkSafety_UR(XYU_list)
    diff = min(diff, ret)


    if diff != float("inf"):
        print( int(diff * 10) )
    else:
        print("SAFE")


def rotate(XYU_list :list):
    for i in range(len(XYU_list)):
        x,y,u = XYU_list[i][0], XYU_list[i][1], XYU_list[i][2]
        
        x2 = -y
        y2 = x
        
        if u == "U":  u2 = "L"
        if u == "D":  u2 = "R"
        if u == "L":  u2 = "D"
        if u == "R":  u2 = "U"
        
        XYU_list[i] = [x2,y2,u2]


def checkSafety_UD(XYU_list :list) -> int:
    check_UD = {}

    for x,y,u in XYU_list:
        if (u == "U") or (u == "D"):
            check_UD.setdefault( x , [] )
            check_UD[x].append( (y,u) )

    for key in check_UD:
        check_UD[key].sort()


    diff_min = float("inf")
    
    for arr in check_UD.values():
        for i in range(len(arr) - 1):
            if (arr[i][1] == "U") and (arr[i+1][1] == "D"):
                diff_min = min( diff_min, (arr[i+1][0] - arr[i][0]) / 2 )

    return diff_min


def checkSafety_UR(XYU_list) -> int:
    check_UR = {}

    for x,y,u in XYU_list:
        if (u == "U") or (u == "R"):
            check_UR.setdefault( (x+y) , [] )
            check_UR[ (x+y) ].append( (x,u) )

    for key in check_UR:
        check_UR[key].sort()


    diff_min = float("inf")
    
    for arr in check_UR.values():
        for i in range(len(arr) - 1):
            if (arr[i][1] == "R") and (arr[i+1][1] == "U"):
                diff_min = min( diff_min, (arr[i+1][0] - arr[i][0]) )

    return diff_min


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def generate_test_case():
    import random
    random.seed(0)
    ret = list()
    n = 10
    for _ in range(5):
        plane_list = list()
        for _ in range(n):
            x, y = random.choices(range(200001), k=2)
            u = random.choice(['U', 'R', 'D', 'L'])
            plane_list.append((x, y, u))
        ret.append({
            'n': n,
            'plane_list': plane_list
        })
    return ret


def solve_simply(N, plane_list):
    # 1単位時間（5秒）ごとに衝突判定：O(N * max(X_1, Y_1, ..., X_N, Y_N))
    from collections import defaultdict
    occur_collision = False
    LIMIT_T = 200000 * 2
    t = 1
    while t <= LIMIT_T:
        location = defaultdict(int)
        same_location = False
        for plane in plane_list:
            x, y, u = plane
            x *= 2  # 移動単位が0.5なので2倍して格子点上に並べる
            y *= 2
            if u == 'U':
                y += t  # 座標はxy方向に2倍されているので速度は単位時間あたり1。
            elif u == 'R':
                x += t
            elif u == 'D':
                y -= t
            else:
                x -= t
            if location[(x, y)] > 0:
                same_location = True
                break
            location[(x, y)] += 1
        if same_location:
            occur_collision = True
            break
        t += 1
    if occur_collision:
        return t * 5
    else:
        return 'SAFE'


def get_min_t_on_same_line(N, plane_list, t_inf=2*(10**6)):
    import bisect
    from collections import defaultdict
    uy, dy = defaultdict(list), defaultdict(list)
    plane_list.sort(key=lambda p: (p[0], p[1]))  # sort by (x, y)
    for plane in plane_list:
        x, y, u = plane
        if u == 'U':
            uy[x].append(y)
        elif u == 'D':
            dy[x].append(y)
    lx, rx = defaultdict(list), defaultdict(list)
    plane_list.sort(key=lambda p: (p[1], p[0]))  # sort by (y, x)
    for plane in plane_list:
        x, y, u = plane
        if u == 'R':
            rx[y].append(x)
        elif u == 'L':
            lx[y].append(x)
    min_t = t_inf
    for y in rx.keys():  # 右向きの飛行機の対になる左向き飛行機の探索
        for x in rx[y]:
            index = bisect.bisect_right(lx[y], x)
            if index >= len(lx[y]):
                continue
            dist = lx[y][index] - x
            min_t = min(min_t, 5 * dist)
    for x in uy.keys():  # 上向きの飛行機の対になる下向き飛行機の探索
        for y in uy[x]:
            index = bisect.bisect_right(dy[x], y)
            if index >= len(dy[x]):
                continue
            dist = dy[x][index] - y
            min_t = min(min_t, 5 * dist)
    return min_t


def get_min_t_at_crossing(N, plane_list, t_inf=2*(10**6)):
    from collections import defaultdict
    import bisect
    plane_list.sort(key=lambda p: p[0])  # sort by x
    min_t = t_inf
    # (1) RU / LDの衝突：点をy+x=kのkで分類
    rx, ux = defaultdict(list), defaultdict(list)
    lx, dx = defaultdict(list), defaultdict(list)
    for plane in plane_list:
        x, y, u = plane
        k = y + x
        if u == 'U':
            ux[k].append(x)
        elif u == 'R':
            rx[k].append(x)
        elif u == 'D':
            dx[k].append(x)
        else:
            lx[k].append(x)
    for k in rx.keys():  # 右向きの飛行機の対になる上向き飛行機の探索
        for x in rx[k]:
            index = bisect.bisect_right(ux[k], x)
            if index >= len(ux[k]):
                continue
            x_diff = ux[k][index] - x
            min_t = min(min_t, 10 * x_diff)
    for k in dx.keys():  # 下向きの飛行機の対になる左向き飛行機の探索
        for x in dx[k]:
            index = bisect.bisect_right(lx[k], x)
            if index >= len(lx[k]):
                continue
            x_diff = lx[k][index] - x
            min_t = min(min_t, 10 * x_diff)
    # (2) RD / LUの衝突：点をy-x=kのkで分類
    rx, ux = defaultdict(list), defaultdict(list)
    lx, dx = defaultdict(list), defaultdict(list)
    for plane in plane_list:
        x, y, u = plane
        k = y - x
        if u == 'U':
            ux[k].append(x)
        elif u == 'R':
            rx[k].append(x)
        elif u == 'D':
            dx[k].append(x)
        else:
            lx[k].append(x)
    for k in rx.keys():  # 右向きの飛行機の対になる下向き飛行機の探索
        for x in rx[k]:
            index = bisect.bisect_right(dx[k], x)
            if index >= len(dx[k]):
                continue
            x_diff = dx[k][index] - x
            min_t = min(min_t, 10 * x_diff)
    for k in ux.keys():  # 上向きの飛行機の対になる左向き飛行機の探索
        for x in ux[k]:
            index = bisect.bisect_right(lx[k], x)
            if index >= len(lx[k]):
                continue
            x_diff = lx[k][index] - x
            min_t = min(min_t, 10 * x_diff)
    return min_t


def solve(N, plane_list):
    T_INF = 2 * (10 ** 6)
    # 同一直線上での衝突の探索
    min_t = get_min_t_on_same_line(N, plane_list, T_INF)
    # クロス衝突の探索
    min_t = min(min_t, get_min_t_at_crossing(N, plane_list, T_INF))
    if min_t == T_INF:
        return 'SAFE'
    return min_t


def main():
    N = int(input())
    plane_list = list()
    for _ in range(N):
        X, Y, U = input().split()
        X, Y = int(X), int(Y)
        plane_list.append((X, Y, U))
    print(solve(N, plane_list))


def check():
    for i, test_case in enumerate(generate_test_case()):
        print('Check {}-th test case'.format(i))
        N, plane_list = test_case['n'], test_case['plane_list']
        assert solve_simply(N, plane_list) == solve(N, plane_list)
    print('OK')


if __name__ == '__main__':
    main()
    # check()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
C = [list(input().split()) for i in range(n)]
A = []
l = 2*10**5 + 5
# l = 100

D = {"U": 0, "R": 1, "D": 2, "L": 3}
for i in range(n):
    A.append([int(C[i][0]), int(C[i][1]), D[C[i][2]]])

from bisect import bisect

ans = float("inf")
for ii in range(4):

    # 正面衝突
    if ii <= 1:
        L = [[] for i in range(l)]
        R = [[] for i in range(l)]
        for i in range(n):
            if A[i][2] == 3:
                L[A[i][1]].append(A[i][0])
            if A[i][2] == 1:
                R[A[i][1]].append(A[i][0])

        for i in range(l):
            # print(L[i],R[i])
            for j in range(len(L[i])):
                ind = bisect(R[i], L[i][j])
                if ind > 0:
                    ans = min(ans, (L[i][j]-R[i][ind-1]) * 5)

    # 90度の衝突
    D = [[] for i in range(2*l)]
    L = [[] for i in range(2*l)]

    for i in range(n):
        if A[i][2] == 3:
            L[A[i][0] + A[i][1]].append(A[i][0])
        if A[i][2] == 2:
            D[A[i][0] + A[i][1]].append(A[i][0])
    for i in range(2*l):
        for j in range(len(L[i])):
            ind = bisect(D[i], L[i][j])
            if ind > 0:
                ans = min(ans, (L[i][j]-D[i][ind-1]) * 10)

    for i in range(n):
        l2 = l // 2
        A[i][0], A[i][1] = (A[i][1]-l2) + l2, -(A[i][0]-l2) + l2
        A[i][2] = (A[i][2] + 1) % 4

if ans == float("inf"):
    ans = "SAFE"
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
C = [list(input().split()) for i in range(n)]
A = []
l = 2*10**5 + 5
# l = 100

D = {"U": 0, "R": 1, "D": 2, "L": 3}
for i in range(n):
    A.append([int(C[i][0]), int(C[i][1]), D[C[i][2]]])

from bisect import bisect

ans = float("inf")
for ii in range(4):

    # 正面衝突
    if ii <= 1:
        L = [[] for i in range(l)]
        R = [[] for i in range(l)]
        for i in range(n):
            if A[i][2] == 3:
                L[A[i][1]].append(A[i][0])
            if A[i][2] == 1:
                R[A[i][1]].append(A[i][0])

        for i in range(l):
            # print(L[i],R[i])
            for j in range(len(L[i])):
                ind = bisect(R[i], L[i][j])
                if ind > 0:
                    ans = min(ans, (L[i][j]-R[i][ind-1]) * 5)

    # 90度の衝突
    D = [[] for i in range(2*l)]
    L = [[] for i in range(2*l)]

    for i in range(n):
        if A[i][2] == 3:
            L[A[i][0] + A[i][1]].append(A[i][0])
        if A[i][2] == 2:
            D[A[i][0] + A[i][1]].append(A[i][0])
    for i in range(2*l):
        for j in range(len(L[i])):
            ind = bisect(D[i], L[i][j])
            if ind > 0:
                ans = min(ans, (L[i][j]-D[i][ind-1]) * 10)

    for i in range(n):
        A[i][0], A[i][1] = A[i][1], -A[i][0]
        A[i][2] = (A[i][2] + 1) % 4

if ans == float("inf"):
    ans = "SAFE"
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
import bisect


n = int(input())
info = []
for i in range(n):
    x, y, u = input().split()
    info.append((int(x), int(y), u))
INF = 10 ** 18


info = sorted(info, key=itemgetter(0))
u = {}
d = {}
l = {}
r = {}
for x, y, dire in info:
    xy = x + y
    if dire == "U":
        if xy not in u:
            u[xy] = []
        u[xy].append(x)
    if dire == "D":
        if xy not in d:
            d[xy] = []
        d[xy].append(x)
    if dire == "L":
        if xy not in l:
            l[xy] = []
        l[xy].append(x)
    if dire == "R":
        if xy not in r:
            r[xy] = []
        r[xy].append(x)
      
ans = INF
for xy in u:
    if xy not in r:
        continue
    for x in u[xy]:
        ind = bisect.bisect_left(r[xy], x) - 1
        if ind < 0:
            continue
        ans = min((x - r[xy][ind]) * 10, ans)

for xy in l:
    if xy not in u:
        continue
    for x in l[xy]:
        ind = bisect.bisect_left(u[xy], x) - 1
        if ind < 0:
            continue
        ans = min((x - u[xy][ind]) * 10, ans)

for xy in d:
    if xy not in r:
        continue
    for x in d[xy]:
        ind = bisect.bisect_left(r[xy], x) - 1
        if ind < 0:
            continue
        ans = min((x - r[xy][ind]) * 10, ans)

for xy in l:
    if xy not in u:
        continue
    for x in l[xy]:
        ind = bisect.bisect_left(u[xy], x) - 1
        if ind < 0:
            continue
        ans = min((x - u[xy][ind]) * 10, ans)

l = {}
r = {}
for x, y, dire in info:
    if dire == "L":
        if y not in l:
            l[y] = []
        l[y].append(x)
    if dire == "R":
        if y not in r:
            r[y] = []
        r[y].append(x)

for y in l:
    if y not in r:
        continue
    for x in l[y]:
        ind = bisect.bisect_left(r[y], x) - 1
        if ind < 0:
            continue
        ans = min((x - r[y][ind]) * 5, ans)

info = sorted(info, key=itemgetter(1))
u = {}
d = {}
for x, y, dire in info:
    if dire == "U":
        if x not in u:
            u[x] = []
        u[x].append(y)
    if dire == "D":
        if x not in d:
            d[x] = []
        d[x].append(y)

for x in d:
    if x not in u:
        continue
    for y in d[x]:
        ind = bisect.bisect_left(u[x], y) - 1
        if ind < 0:
            continue
        ans = min((y - u[x][ind]) * 5, ans)

if ans == INF:
    print("SAFE")
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
import bisect


n = int(input())
info = []
for i in range(n):
    x, y, u = input().split()
    info.append((int(x), int(y), u))
INF = 10 ** 18


info = sorted(info, key=itemgetter(0))
u = {}
d = {}
l = {}
r = {}
for x, y, dire in info:
    xy = x + y
    if dire == "U":
        if xy not in u:
            u[xy] = []
        u[xy].append(x)
    if dire == "D":
        if xy not in d:
            d[xy] = []
        d[xy].append(x)
    if dire == "L":
        if xy not in l:
            l[xy] = []
        l[xy].append(x)
    if dire == "R":
        if xy not in r:
            r[xy] = []
        r[xy].append(x)
      
ans = INF
for xy in u:
    if xy not in r:
        continue
    for x in u[xy]:
        ind = bisect.bisect_left(r[xy], x) - 1
        if ind < 0:
            continue
        ans = min((x - r[xy][ind]) * 10, ans)


for xy in l:
    if xy not in d:
        continue
    for x in l[xy]:
        ind = bisect.bisect_left(d[xy], x) - 1
        if ind < 0:
            continue
        ans = min((x - d[xy][ind]) * 10, ans)

l = {}
r = {}
for x, y, dire in info:
    if dire == "L":
        if y not in l:
            l[y] = []
        l[y].append(x)
    if dire == "R":
        if y not in r:
            r[y] = []
        r[y].append(x)

for y in l:
    if y not in r:
        continue
    for x in l[y]:
        ind = bisect.bisect_left(r[y], x) - 1
        if ind < 0:
            continue
        ans = min((x - r[y][ind]) * 5, ans)


info = sorted(info, key=itemgetter(1))
u = {}
d = {}
for x, y, dire in info:
    if dire == "U":
        if x not in u:
            u[x] = []
        u[x].append(y)
    if dire == "D":
        if x not in d:
            d[x] = []
        d[x].append(y)

for x in d:
    if x not in u:
        continue
    for y in d[x]:
        ind = bisect.bisect_left(u[x], y) - 1
        if ind < 0:
            continue
        ans = min((y - u[x][ind]) * 5, ans)

if ans == INF:
    print("SAFE")
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
import bisect
import sys
input = sys.stdin.buffer.readline


n = int(input())
info = []
for i in range(n):
    x, y, u = input().split()
    info.append((int(x), int(y), u))
INF = 10 ** 18


info = sorted(info, key=itemgetter(0))
u = {}
d = {}
l = {}
r = {}
for x, y, dire in info:
    xy = x + y
    if dire == "U":
        if xy not in u:
            u[xy] = []
        u[xy].append(x)
    if dire == "D":
        if xy not in d:
            d[xy] = []
        d[xy].append(x)
    if dire == "L":
        if xy not in l:
            l[xy] = []
        l[xy].append(x)
    if dire == "R":
        if xy not in r:
            r[xy] = []
        r[xy].append(x)
      
ans = INF
for xy in u:
    if xy not in r:
        continue
    for x in u[xy]:
        ind = bisect.bisect_left(r[xy], x) - 1
        if ind < 0:
            continue
        ans = min((x - r[xy][ind]) * 10, ans)


for xy in l:
    if xy not in d:
        continue
    for x in l[xy]:
        ind = bisect.bisect_left(d[xy], x) - 1
        if ind < 0:
            continue
        ans = min((x - d[xy][ind]) * 10, ans)

l = {}
r = {}
for x, y, dire in info:
    if dire == "L":
        if y not in l:
            l[y] = []
        l[y].append(x)
    if dire == "R":
        if y not in r:
            r[y] = []
        r[y].append(x)

for y in l:
    if y not in r:
        continue
    for x in l[y]:
        ind = bisect.bisect_left(r[y], x) - 1
        if ind < 0:
            continue
        ans = min((x - r[y][ind]) * 5, ans)


info = sorted(info, key=itemgetter(1))
u = {}
d = {}
for x, y, dire in info:
    if dire == "U":
        if x not in u:
            u[x] = []
        u[x].append(y)
    if dire == "D":
        if x not in d:
            d[x] = []
        d[x].append(y)

for x in d:
    if x not in u:
        continue
    for y in d[x]:
        ind = bisect.bisect_left(u[x], y) - 1
        if ind < 0:
            continue
        ans = min((y - u[x][ind]) * 5, ans)

if ans == INF:
    print("SAFE")
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

xyu_s = []
for _ in range(n):
    xyu = list(input().split())
    xyu = [int(xyu[0]), int(xyu[1]), str(xyu[2])]
    xyu_s.append(xyu)

state = "SAFE"

def change_u(dir):
    if dir == "U":
        return "D"
    elif dir == "R":
        return "L"
    elif dir == "D":
        return "U"
    else:
        return "R"

for i in range(n):
    x = xyu_s[i][0]
    y = xyu_s[i][1]
    u = xyu_s[i][2]
    for j in range(i, n):
        x2 = xyu_s[j][0]
        y2 = xyu_s[j][1]
        u2 = xyu_s[j][2]
        if x == x2:
            if u == "U" and u2 == "D" and y2 - y > 0:
                state = int((y2 - y) / 2 * 10)
            elif u == "D" and u2 == "U" and y - y2 > 0:
                state = int((y - y2) / 2 * 10)
        elif y == y2:
            if u == "R" and u2 == "L" and x2 - x > 0:
                state = int((x2 - x) / 2 * 10)
            elif u == "L" and u2 == "R" and x - x2 > 0:
                state = int((x - x2) / 2 * 10)
        elif x - x2 > 0 and x - x2 == y2 - y:
            if (u == "U" and u2 == "R") or (u == "L" and u2 == "D"):
                state = (x - x2) * 10
        elif x2 - x > 0 and x2 - x == y - y2:
            if (u == "D" and u2 == "L") or (u == "R" and u2 == "U"):
                state = (x2 - x) * 10
        elif x2 - x > 0 and x2 - x == y2 - y:
            if (u == "U" and u2 == "L") or (u == "R" and u2 == "D"):
                state = (x2 - x) * 10
        elif x - x2 > 0 and x - x2 == y - y2:
            if (u == "L" and u2 == "U") or (u == "D" and u2 == "R"):
                state = (x - x2) * 10

print(state)

Submission status: Wrong Answer

Solution code:
n = int(input())

xyu_s = []
for _ in range(n):
    xyu = list(input().split())
    xyu = [int(xyu[0]), int(xyu[1]), str(xyu[2])]
    xyu_s.append(xyu)

state = "SAFE"

def change_u(dir):
    if dir == "U":
        return "D"
    elif dir == "R":
        return "L"
    elif dir == "D":
        return "U"
    else:
        return "R"

for i in range(n):
    x = xyu_s[i][0]
    y = xyu_s[i][1]
    u = xyu_s[i][2]
    u_change = change_u(u)
    for j in range(i, n):
        x2 = xyu_s[j][0]
        y2 = xyu_s[j][1]
        u2 = xyu_s[j][2]
        if x == x2 and u_change == u2:
            y_diff = abs(y - y2)
            state = int(y_diff / 2 * 10)
        elif y == y2 and u_change == u2:
            x_diff = abs(x - x2)
            state = int(x_diff / 2 * 10)
            
        elif x - x2 > 0 and x - x2 == y2 - y:
            if (u == "U" and u2 == "R") or (u == "L" and u2 == "D"):
                state = (x - x2) * 10
        elif x2 - x > 0 and x2 - x == y - y2:
            if (u == "D" and u2 == "L") or (u == "R" and u2 == "U"):
                state = (x2 - x) * 10
        elif x2 - x > 0 and x2 - x == y2 - y:
            if (u == "U" and u2 == "L") or (u == "R" and u2 == "D"):
                state = (x2 - x) * 10
        elif x - x2 > 0 and x - x2 == y - y2:
            if (u == "L" and u2 == "U") or (u == "D" and u2 == "R"):
                state = (x - x2) * 10

print(state)

Submission status: Wrong Answer

Solution code:
n = int(input())

xyu_s = []
for _ in range(n):
    xyu = list(input().split())
    xyu = [int(xyu[0]), int(xyu[1]), str(xyu[2])]
    xyu_s.append(xyu)

state = "SAFE"

def change_u(dir):
    if dir == "U":
        return "D"
    elif dir == "R":
        return "L"
    elif dir == "D":
        return "U"
    else:
        return "R"

for i in range(n):
    x = xyu_s[i][0]
    y = xyu_s[i][1]
    u = xyu_s[i][2]
    u_change = change_u(u)
    for j in range(i, n):
        if x == xyu_s[j][0] and u_change == xyu_s[j][2]:
            y_diff = abs(y - xyu_s[j][1])
            if y_diff % 2 == 0:
                state = y_diff / 2 * 10

        if y == xyu_s[j][1] and u_change == xyu_s[j][2]:
            x_diff = abs(x - xyu_s[j][0])
            if x_diff % 2 == 0:
                state = int(x_diff / 2 * 10)

print(state)

Submission status: Wrong Answer

Solution code:
from itertools import chain

def getInt():
  return int(input())

def getInts():
  return list(map(int, input().split()))

def getFromLines(n, getA):
  l = []
  for i in range(n):
    l.append(getA())
  return l

n = getInt() # Int
rPlanes = [] # [(Int,Int)]
lPlanes = [] # [(Int,Int)]
uPlanes = [] # [(Int,Int)]
dPlanes = [] # [(Int,Int)]

for i in range(n):
  (x,y,oStr) = input().split()
  (x,y) = (int(x), int(y))
  if oStr == 'U':
    uPlanes.append((x,y))
  elif oStr == 'R':
    rPlanes.append((x,y))
  elif oStr == 'D':
    dPlanes.append((x,y))
  elif oStr == 'L':
    lPlanes.append((x,y))
  else:
    assert(False)

def urClashTime(uPlanes, rPlanes):
  distances = []
  for (uX,uY) in uPlanes:
    for (rX,rY) in rPlanes:
      deltaX = uX - rX
      if deltaX > 0 and deltaX == rY - uY: # if clashes
          distances.append(deltaX * 10)
  return distances

def udClashTime(uPlanes, dPlanes):
  distances = []
  for (uX,uY) in uPlanes:
    for (dX,dY) in dPlanes:
      deltaY = dY - uY
      if uX == dX and deltaY > 0: # if clashes
          distances.append(deltaY * 5)
  return distances

def rotN90(cors):
  return map(lambda cor: (cor[1], -cor[0]), cors)
def rot90(cors):
  return map(lambda cor: (-cor[1], cor[0]), cors)
def rot180(cors):
  return map(lambda cor: (-cor[0], -cor[1]), cors)


ur = urClashTime(uPlanes, rPlanes)
ul = urClashTime(rotN90(lPlanes), rotN90(uPlanes))
rd = urClashTime(rot90(rPlanes), rot90(dPlanes))
dl = urClashTime(rot180(dPlanes), rot180(lPlanes))

ud = udClashTime(uPlanes, dPlanes)
rl = udClashTime(rot90(rPlanes), rot90(lPlanes))


times = ur+ul+rd+dl+ud+rl
if times:
  print(min(times))
else:
  print("SAFE")

Submission status: Wrong Answer

Solution code:
from itertools import chain

def getInt():
  return int(input())

def getInts():
  return list(map(int, input().split()))

def getFromLines(n, getA):
  l = []
  for i in range(n):
    l.append(getA())
  return l

n = getInt() # Int
rPlanes = [] # [(Int,Int)]
lPlanes = [] # [(Int,Int)]
uPlanes = [] # [(Int,Int)]
dPlanes = [] # [(Int,Int)]

for i in range(n):
  (x,y,oStr) = input().split()
  (x,y) = (int(x), int(y))
  if oStr == 'U':
    uPlanes.append((x,y))
  elif oStr == 'R':
    rPlanes.append((x,y))
  elif oStr == 'D':
    dPlanes.append((x,y))
  elif oStr == 'L':
    lPlanes.append((x,y))
  else:
    assert(False)

def urClashTime(uPlanes, rPlanes):
  distance = -1
  for (uX,uY) in uPlanes:
    for (rX,rY) in rPlanes:

      deltaX = uX - rX
      if deltaX > 0 and deltaX == rY - uY: # if clashes
        if distance == -1 or deltaX < distance:
          distance = deltaX
  return distance * 10

def udClashTime(uPlanes, dPlanes):
  distance = -1
  for (uX,uY) in uPlanes:
    for (dX,dY) in dPlanes:
      deltaY = dY - uY
      if uX == dX and deltaY > 0: # if clashes
        if distance == -1 or deltaY < distance:
          distance = deltaY
  return distance * 5

def rotN90(cors):
  return map(lambda cor: (cor[1], -cor[0]), cors)
def rot90(cors):
  return map(lambda cor: (-cor[1], cor[0]), cors)
def rot180(cors):
  return map(lambda cor: (-cor[0], -cor[1]), cors)


ur = urClashTime(uPlanes, rPlanes)
ud = udClashTime(uPlanes, dPlanes)
ul = urClashTime(rotN90(lPlanes), rotN90(uPlanes))
rd = urClashTime(rot90(rPlanes), rot90(dPlanes))
rl = udClashTime(rot90(rPlanes), rot90(lPlanes))
dl = urClashTime(rot180(dPlanes), rot180(lPlanes))

clashTime = -1
for t in [ur, ud, ul, rd, rl, dl]:
  if t > 0 and (clashTime < 0 or t < clashTime):
    clashTime = t

if clashTime < 0:
  print("SAFE")
else:
  print(clashTime)