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 numpy as np

def convert(char):
  if char == 'U':
    return 1
  if char == 'R':
    return 2
  if char == 'D':
    return 3
  if char == 'L':
    return 4

n = int(input())
x = np.empty(n)
y = np.empty(n)
u = np.empty(n)
for i in range(n):
  xyu = input().split()
  x[i] = int(xyu[0])
  y[i] = int(xyu[1])
  u[i] = convert(xyu[2])

time = 1000
for t in range(time):
  air_planes = set()
  for i in range(n):
    if u[i] == 1:
      y[i] += 0.1
    if u[i] == 2:
      x[i] += 0.1
    if u[i] == 3:
      y[i] -= 0.1
    if u[i] == 4:
      x[i] -= 0.1
    place = x[i] * 10**6 + y[i]
    if place in air_planes:
      print(t+1)
      exit()
    else:
      air_planes.add(place)
print('SAFE')

Submission status: Wrong Answer

Solution code:
n = int(input())
grid = []
u = []
for _ in range(n):
    x, y, p = input().split()
    grid.append([int(x),int(y)])
    u.append(str(p))

cnt = 0
outside = [False for _ in range(n)]
break_flg = False
while True:
    for i in range(n):
        if u[i] == 'U':
            grid[i][1] += 1
            if grid[i][1] > 0: outside[i] = True
        if u[i] == 'R':
            grid[i][0] += 1
            if grid[i][0] > 0: outside[i] = True
        if u[i] == 'D':
            grid[i][1] -= 1
            if grid[i][1] < 0: outside[i] = True
        if u[i] == 'L':
            grid[i][0] -= 1
            if grid[i][0] < 0: outside[i] = True
    if all(outside):
        print("SAFE")
        break

    cnt += 10

    for i in range(n):
        for j in range(i+1, n):
            if grid[i][0] == grid[j][0] and grid[i][1] == grid[j][1]:
                break_flg = True
                print(cnt)
                break;
    if break_flg: break

Submission status: Wrong Answer

Solution code:
import copy
N = int(input())
XYUs = [list(map(str,input().split())) for _ in range(N)]

up_slopes = [[] for _ in range(400005)]
down_slopes = [[] for _ in range(400005)]
xs = [[] for _ in range(200005)]
ys = [[] for _ in range(200005)]



for XYU in XYUs:
    #y切片
    up_slopes[int(XYU[1])-int(XYU[0])+200000].append([int(XYU[0]),XYU[2]])
    down_slopes[int(XYU[1])+int(XYU[0])].append([int(XYU[0]),XYU[2]])
    xs[int(XYU[0])].append([int(XYU[1]),XYU[2]])
    ys[int(XYU[1])].append([int(XYU[0]),XYU[2]])
    
min_val = int(1e+100)
for up_slope in up_slopes:
    U_posi = -1
    R_posi = -1
    incidents = copy.deepcopy(up_slope)
    incidents = sorted(incidents)
    for incident in up_slope:
        if incident[1] == "U":
            U_posi = incident[0]
        elif incident[1] == "R":
            R_posi = incident[0]
        elif incident[1] == "D" and R_posi != -1:
            accident = incident[0]-R_posi
            if min_val > accident:
                min_val = accident
        elif incident[1] == "L" and U_posi != -1:
            accident = incident[0]-U_posi
            if min_val > accident:
                min_val = accident

for down_slope in down_slopes:
    D_posi = -1
    R_posi = -1
    incidents = copy.deepcopy(down_slope)
    incidents = sorted(incidents)
    for incident in incidents:
        if incident[1] == "D":
            D_posi = incident[0]
        elif incident[1] == "R":
            R_posi = incident[0]
        elif incident[1] == "U" and R_posi != -1:
            accident = incident[0]-R_posi
            if min_val > accident:
                min_val = accident
        elif incident[1] == "L" and D_posi != -1:
            accident = incident[0]-D_posi
            if min_val > accident:
                min_val = accident


for x in xs:
    U_posi = -1
    incidents = copy.deepcopy(x)
    incidents = sorted(incidents)
    for incident in incidents:
        if incident[1] == "U":
            U_posi = incident[0]
        elif incident[1] == "D" and U_posi!=-1:
            if min_val > (incident[0]-U_posi)/2:
                min_val = (incident[0]-U_posi)/2
            
for y in ys:
    R_posi = -1
    incidents = copy.deepcopy(y)
    incidents = sorted(incidents)
    for incident in incidents:
        if incident[1] == "R":
            R_posi = incident[0]
        elif incident[1] == "L" and R_posi!=-1:
            if min_val > (incident[0]-R_posi)/2:
                min_val = (incident[0]-R_posi)/2
if min_val < 300000:
    print(int(min_val*10))
else:
    print("SAFE")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import bisect

n = int(input())
# x, yの値 URDLの順
p = [[] for _ in range(4)]
# xに対するyの値 URDLの順
px = [defaultdict(list) for _ in range(4)]
# yに対するyの値 URDLの順
py = [defaultdict(list) for _ in range(4)]
# x, yの和　URDLの順
s = [defaultdict(list) for _ in range(4)]
# x, yの差　URDLの順
d = [defaultdict(list) for _ in range(4)]

directions = {"U":0, "R":1, "D":2, "L":3}

for i in range(n):
    x, y, u = input().split()
    x = int(x)
    y = int(y)
    p.append([x, y])
    px[directions[u]][x].append(y)
    py[directions[u]][y].append(x)
    s[directions[u]][x+y].append([x, y])
    d[directions[u]][x-y].append([x, y])

ans = 10**9

# R, Uパターン
keys = list(s[directions["R"]].keys())
for k in keys:
    for rx, ry in s[directions["R"]][k]:
        for ux, uy in s[directions["U"]][k]:
            if rx > ux:
                continue
            ans = min(ans, abs(rx-ux)*10)
# L, Dパターン
keys = list(s[directions["L"]].keys())
for k in keys:
    for lx, ly in s[directions["L"]][k]:
        for dx, dy in s[directions["D"]][k]:
            if lx < dx:
                continue
            ans = min(ans, abs(lx-dx)*10)
# L, Uパターン
keys = list(s[directions["L"]].keys())
for k in keys:
    for lx, ly in s[directions["L"]][k]:
        for ux, uy in s[directions["U"]][k]:
            if lx < ux:
                continue
            ans = min(ans, abs(lx-ux)*10)
# R, Dパターン
keys = list(s[directions["R"]].keys())
for k in keys:
    for rx, ry in s[directions["R"]][k]:
        for dx, dy in s[directions["D"]][k]:
            if rx > dx:
                break
            ans = min(ans, abs(rx-dx)*10)

# U, Dパターン
keys = list(px[directions["U"]].keys())
for k in keys:
    if len(px[directions["D"]][k]) == 0:
        continue
    px[directions["D"]][k].sort()
    for uy in px[directions["U"]][k]:
        if uy > px[directions["D"]][k][-1]:
            break
        pos = bisect.bisect_left(px[directions["D"]][k], uy)
        ans = min(ans, (px[directions["D"]][k][pos]-uy)*5)

# R, Lパターン
keys = list(py[directions["R"]].keys())
for k in keys:
    if len(py[directions["L"]][k]) == 0:
        continue
    py[directions["L"]][k].sort()
    for uy in py[directions["R"]][k]:
        if uy > py[directions["L"]][k][-1]:
            break
        pos = bisect.bisect_left(py[directions["L"]][k], uy)
        ans = min(ans, (py[directions["L"]][k][pos]-uy)*5)

if ans == 10**9:
    ans = "SAFE"
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = [0]*n
y = [0]*n

ux = [0]*n
uy = [0]*n


for i in range(n):
    x[i],y[i],u =  input().split()
    if u=="U":
        uy[i] =1
    elif u=="R":
        ux[i] =1
    elif u=="D":
        uy[i] =-1
    elif u=="L":
        ux[i] =-1
    x[i]= int(x[i])
    y[i]= int(y[i])
time = 2*10**7
for i in range(n):
    for j in range(n-1-i):

            if x[i]-x[i+1+j] == 0 and  y[i]-y[i+1+j] == 0:
                time = min(time,0)
            elif x[i]-x[i+1+j] == 0 and uy[i]*uy[i+1+j]==-1 and (y[i]-y[i+1+j])*uy[i]<0:
                time = min(time,abs((y[i]-y[i+1+j])/0.2))
            elif y[i]-y[i+1+j] == 0 and ux[i]*ux[i+1+j]==-1 and (x[i]-x[i+1+j])*ux[i]<0:
                time = min(time,abs((x[i]-x[i+1+j])/0.2))
            elif (ux[i]-ux[i+1+j])==0 or (uy[i]-uy[i+1+j])==0:
                time =time
            elif (x[i]-x[i+1+j]) /(ux[i]-ux[i+1+j]) ==(y[i]-y[i+1+j]) /(uy[i]-uy[i+1+j]):
                time = min(time,abs((x[i]-x[i+1+j])/0.1))

if time == 2*10**7:
    print("SAFE")
else:
    print(int(time))

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
airplanes = []
for _ in range(N):
  x, y, u = input().strip().split()
  airplanes.append((int(x), int(y), u))

hugou = {"U": 1, "R": 1, "D": -1, "L": -1}

def judge(A, B):
  if A[2] == B[2]:
    return math.inf
  elif A[2] == "U" and B[2] == "D":
    return abs(A[1] - B[1]) * 5 if A[0] == B[0] else math.inf
  elif A[2] == "R" and B[2] == "L":
    return abs(A[0] - B[0]) * 5 if A[1] == B[1] else math.inf
  else:
    dx = B[0] * hugou[B[2]] - A[0] * hugou[A[2]]
    dy = B[1] * hugou[B[2]] - A[1] * hugou[A[2]]
    if dx + dy == 0:
      return abs(dx * 10)
    else:
      return math.inf
    
deadline = math.inf
for i in range(N-1):
  for j in range(i+1, N):
    tmp = judge(airplanes[i], airplanes[j])
    if tmp < deadline: deadline = tmp

print(deadline)

Submission status: Wrong Answer

Solution code:
N = int(input())
plane = [0] * N
houkou = ["U", "D", "R", "L"]
for i in range(N):
  x, y, p = list(map(str, input().split()))
  x = int(x)
  y = int(y)
  p2 = houkou.index(p)
  plane[i] = [x, y, x + y, x - y, p2]
  
#x座標が同じでぶつかる
plane = sorted(plane, key=lambda x:x[0])
time = 10 ** 10
for k in range(1, N):
    if plane[k][0] == plane[k - 1][0]:
      if plane[k][1] > plane[k - 1][1]:
        if (plane[k][4] == 1) and (plane[k - 1][4] == 0):
          time2 = (plane[k][1] - plane[k - 1][1]) / 0.2
          time = min(time, time2)
      else:
        if (plane[k][4] == 0) and (plane[k - 1][4] == 1):
          time2 = (plane[k - 1][1] - plane[k][1]) / 0.2
          time = min(time, time2)
        
#y座標が同じでぶつかる
plane = sorted(plane, key=lambda x:x[1])
for k in range(1, N):
    if plane[k][1] == plane[k - 1][1]:
      if plane[k][0] > plane[k - 1][0]:
        if (plane[k][4] == 3) and (plane[k - 1][4] == 2):
          time2 = int((plane[k][0] - plane[k - 1][0]) / 0.2)
          time = min(time, time2)
      else:
        if (plane[k][4] == 2) and (plane[k - 1][4] == 3):
          time2 = int((plane[k - 1][0] - plane[k][0]) / 0.2)
          time = min(time, time2)

def go(x, y, u, t):
  if u == 0:
    return x, int(y + t * 0.1)
  elif u== 1:
    return x, int(y - t * 0.1)
  elif u == 2:
    return int(x + t * 0.1), y
  else:
    return int(x - t * 0.1), y
  
          
#和が同じでぶつかる
plane = sorted(plane, key=lambda x:x[2])
for k in range(1, N):
    one = plane[k]
    two = plane[k - 1]
                
    if plane[k][2] == plane[k - 1][2]:
      time2 = int(abs(one[0] - two[0]) / 0.1)
      max_x = max(one[0],two[0])
      min_x = min(one[0], two[0])
      max_y = max(one[1], two[1])
      min_y = min(one[1], two[1])
      L = [[max_x, max_y], [min_x, min_y]]
      #k
      k_x, k_y = go(one[0], one[1], one[4], time2)
      #k - 1
      k2_x, k2_y = go(two[0], two[1], two[4], time2)
      if [k_x, k_y] in L:
        if [k2_x, k2_y] in L:
          if [k_x, k_y] == [k2_x, k2_y]:
            time = min(time, time2)
          
#差が同じでぶつかる
plane = sorted(plane, key=lambda x:x[3])
#print(plane)
for k in range(1, N):
    one = plane[k]
    two = plane[k - 1]
                
    if plane[k][3] == plane[k - 1][3]:
      time2 = int(abs(one[0] - two[0]) / 0.1)
      max_x = max(one[0],two[0])
      min_x = min(one[0], two[0])
      max_y = max(one[1], two[1])
      min_y = min(one[1], two[1])
      L = [[max_x, min_y], [min_x, max_y]]
      #k
      k_x, k_y = go(one[0], one[1], one[4], time2)
      #k - 1
      k2_x, k2_y = go(two[0], two[1], two[4], time2)
      if [k_x, k_y] in L:
        if [k2_x, k2_y] in L:
          if [k_x, k_y] == [k2_x, k2_y]:
            time = min(time, time2)          
            
if time == 10 ** 10:
  print("SAFE")
else:
  print(int(time))
#print(plane)

Submission status: Wrong Answer

Solution code:
INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

L = 200001
Y = [[[] for _ in range(4)] for _ in range(L)]
X = [[[] for _ in range(4)] for _ in range(L)]

N = int(input())
for i in range(N):
    x, y, u = map(str, input().split())
    x = int(x)
    y = int(y)
    if u == 'U':
        X[x][0].append(y)
    if u == 'D':
        X[x][2].append(y)
    if u == 'R':
        Y[y][1].append(x)
    if u == 'L':
        Y[y][3].append(x)

mn = INF
for i in range(L):
    if X[i][0] and X[i][2]:
        bat = min(X[i][2]) - max(X[i][0])
        if bat < 0:
            continue
        bat *= 5
        mn = min(mn, bat)
    if Y[i][1] and Y[i][3]:
        bat = min(Y[i][3]) - max(Y[i][1])
        if bat < 0:
            continue
        bat *= 5
        mn = min(mn, bat)
    if i > 0:
        if X[i][0] and Y[i][1]:
            mn = min(mn, i * 10)
        if X[i][2] and Y[i][3]:
            mn = min(mn, i * 10)


if mn == INF:
    print('SAFE')
else:
    print(mn)

Submission status: Wrong Answer

Solution code:

import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop
from collections import defaultdict

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)

N = n1()
X = []
Y = []
U = []
ZX = defaultdict(list)
ZY = defaultdict(list)
for i in range(N):
    x, y, u = sn()
    X.append(int(x))
    Y.append(int(y))
    U.append(u)
    ZX[x].append([int(y), u])
    ZY[y].append([int(x), u])

ns_min = 10**10
tmp = ns_min
for k in ZX.keys():
    if len(ZX[k]) >= 2:
        for i in range(len(ZX[k])):
            for j in range(i+1, len(ZX[k])):
                if ZX[k][i][1] == "U" and ZX[k][j][1] == "D" and ZX[k][i][0] < ZX[k][j][0]:
                    tmp = (ZX[k][j][0] - ZX[k][i][0]) / 2
                if ZX[k][i][1] == "D" and ZX[k][j][1] == "U" and ZX[k][i][0] > ZX[k][j][0]:
                    tmp = (ZX[k][i][0] - ZX[k][j][0]) / 2
                if tmp < ns_min: ns_min = tmp                    

ew_min = 10**10
tmp = ew_min
for k in ZY.keys():
    if len(ZY[k]) >= 2:
        for i in range(len(ZY[k])):
            for j in range(i+1, len(ZY[k])):
                if ZY[k][i][1] == "R" and ZY[k][j][1] == "L" and ZY[k][i][0] < ZY[k][j][0]:
                    tmp = (ZY[k][j][0] - ZY[k][i][0]) / 2
                if ZY[k][i][1] == "L" and ZY[k][j][1] == "R" and ZY[k][i][0] > ZY[k][j][0]:
                    tmp = (ZY[k][i][0] - ZY[k][j][0]) / 2
                if tmp < ew_min: ew_min = tmp                    


def trans(a, b):
    return (a+b, b-a)    

ZX = defaultdict(list)
ZY = defaultdict(list)
for i in range(N):
    x, y = trans(X[i], Y[i])
    u = U[i]
    ZX[x].append([int(y), u])
    ZY[y].append([int(x), u])

ns2_min = 10**10
tmp = ns2_min
for k in ZX.keys():
    if len(ZX[k]) >= 2:
        for i in range(len(ZX[k])):
            for j in range(i+1, len(ZX[k])):
                if ZX[k][i][1] == "U" and ZX[k][j][1] == "R" and ZX[k][i][0] < ZX[k][j][0]:
                    tmp = (ZX[k][j][0] - ZX[k][i][0]) / 2
                if ZX[k][i][1] == "D" and ZX[k][j][1] == "L" and ZX[k][i][0] > ZX[k][j][0]:
                    tmp = (ZX[k][i][0] - ZX[k][j][0]) / 2
                if tmp < ns2_min: ns2_min = tmp                    

ew2_min = 10**10
tmp = ew2_min
for k in ZY.keys():
    if len(ZY[k]) >= 2:
        for i in range(len(ZY[k])):
            for j in range(i+1, len(ZY[k])):
                if ZY[k][i][1] == "R" and ZY[k][j][1] == "D" and ZY[k][i][0] < ZY[k][j][0]:
                    tmp = (ZY[k][j][0] - ZY[k][i][0]) / 2
                if ZY[k][i][1] == "L" and ZY[k][j][1] == "U" and ZY[k][i][0] > ZY[k][j][0]:
                    tmp = (ZY[k][i][0] - ZY[k][j][0]) / 2
                if tmp < ew2_min: ew2_min = tmp    

ans = int(min(ns_min, ew_min, ns2_min, ew2_min)*10)
if ans == 100000000000:
    ans = "SAFE"

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = []
min_crash = 2e5
for _ in range(n):
    x, y, u = list(input().split())
    x = int(x)
    y = int(y)
    a_list.append([x, y, u])

min_crash = 2e5
x_sort = sorted(a_list, key=lambda a: a[0])
y_sort = sorted(a_list, key=lambda a: a[1])
for i in range(n):
    if i < n-1 and x_sort[i][2] == "R":
        flag = 1
        for x, y, u in x_sort[i+1:]:
            if (y < x_sort[i][1] and u == "U") or (y > x_sort[i][1] and u == "D"):
                if abs(x_sort[i][0]-x) == abs(x_sort[i][1] - y):
                    crash = x - x_sort[i][0]
                    min_crash = min(min_crash, crash)
            elif flag and y == x_sort[i][1] and u == "L":
                flag = 0
                crash = (x - x_sort[i][0])/2
                min_crash = min(min_crash, crash)

    elif i != 0 and x_sort[i][2] == "L":
        for x, y, u in x_sort[:i]:
            if (y < x_sort[i][1] and u == "U") or (y > x_sort[i][1] and u == "D"):
                if abs(x_sort[i][0]-x) == abs(x_sort[i][1] - y):
                    crash = x_sort[i][0]-x
                    min_crash = min(min_crash, crash)
    
    if i < n-1 and y_sort[i][2] == "U":
        for x, y, u in y_sort[i+1:]:
            if x == y_sort[i][0] and u == "D":
                crash = (y - y_sort[i][1])/2
                min_crash = min(min_crash, crash)
                break


if min_crash == 2e5:
    print("SAFE")
else:
    print(int(min_crash*10))

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]


N = int(readline())
XYU = [readline().decode().split() for _ in range(N)]
XY = [[int(x), int(y)] for x, y, _ in XYU]
U = [u for _, _, u in XYU]

for i in range(1, 100000):
    for idx in range(N):
        if U[idx] == "U":
            XY[idx][1] += 1
        elif U[idx] == "D":
            XY[idx][1] -= 1
        elif U[idx] == "L":
            XY[idx][0] -= 1
        else:
            XY[idx][0] += 1
    if len(get_unique_list(XY)) != N:
        print(i * 10)
        sys.exit()

print('SAFE')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import bisect

n = int(input())
# x, yの値 URDLの順
p = [[] for _ in range(4)]
# xに対するyの値 URDLの順
px = [defaultdict(list) for _ in range(4)]
# yに対するyの値 URDLの順
py = [defaultdict(list) for _ in range(4)]
# x, yの和　URDLの順
s = [defaultdict(list) for _ in range(4)]
# x, yの差　URDLの順
d = [defaultdict(list) for _ in range(4)]

directions = {"U":0, "R":1, "D":2, "L":3}

for i in range(n):
    x, y, u = input().split()
    x = int(x)
    y = int(y)
    p.append([x, y])
    px[directions[u]][x].append(y)
    py[directions[u]][y].append(x)
    s[directions[u]][x+y].append([x, y])
    d[directions[u]][x-y].append([x, y])

ans = 10**9

# R, Uパターン
keys = list(s[directions["R"]].keys())
for k in keys:
    for rx, ry in s[directions["R"]][k]:
        for ux, uy in s[directions["U"]][k]:
            if rx > ux:
                continue
            ans = min(ans, abs(rx-ux)*10)
# L, Dパターン
keys = list(s[directions["L"]].keys())
for k in keys:
    for lx, ly in s[directions["L"]][k]:
        for dx, dy in s[directions["D"]][k]:
            if lx < dx:
                continue
            ans = min(ans, abs(lx-dx)*10)
# L, Uパターン
keys = list(s[directions["L"]].keys())
for k in keys:
    for lx, ly in s[directions["L"]][k]:
        for ux, uy in s[directions["U"]][k]:
            if lx < ux:
                continue
            ans = min(ans, abs(lx-ux)*10)
# R, Dパターン
keys = list(s[directions["R"]].keys())
for k in keys:
    for rx, ry in s[directions["R"]][k]:
        for dx, dy in s[directions["D"]][k]:
            if rx > dx:
                break
            ans = min(ans, abs(rx-dx)*10)

# U, Dパターン
keys = list(px[directions["U"]].keys())
for k in keys:
    if len(px[directions["D"]][k]) == 0:
        continue
    px[directions["D"]][k].sort()
    for uy in px[directions["U"]][k]:
        if uy > px[directions["D"]][k][-1]:
            break
        pos = bisect.bisect_left(px[directions["D"]][k], uy)
        ans = min(ans, (px[directions["D"]][k][pos]-uy)*5)

# R, Lパターン
keys = list(px[directions["R"]].keys())
for k in keys:
    if len(px[directions["L"]][k]) == 0:
        continue
    px[directions["L"]][k].sort()
    for uy in px[directions["R"]][k]:
        if uy > px[directions["L"]][k][-1]:
            break
        pos = bisect.bisect_left(px[directions["L"]][k], uy)
        ans = min(ans, (px[directions["L"]][k][pos]-uy)*5)

if ans == 10**9:
    ans = "SAFE"
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
infos = []
dic = {"L":0,"R":1,"D":1,"U":0}
lr_dic = [defaultdict(list)] * 2 # straight LR
ud_dic =  [defaultdict(list)] * 2 # straight UD
lr_dic_p = [defaultdict(list)] * 2 # x + y LR
ud_dic_p = [defaultdict(list)] * 2 # x + y UD
lr_dic_m = [defaultdict(list)] * 2 # -x + y LR
ud_dic_m = [defaultdict(list)] * 2 # -x + y UD


for i in range(n):
    x,y,u = input().split()
    x = int(x)
    y = int(y)
    if u == "R" or u == "L":
        lr_dic[dic[u]][y].append(x)
        lr_dic_p[dic[u]][x+y].append(y)
        lr_dic_m[dic[u]][-x+y].append(y)
    else:
        ud_dic[dic[u]][x].append(y)
        ud_dic_p[dic[u]][x+y].append(x)
        ud_dic_m[dic[u]][-x+y].append(x)
    infos.append((u,x,y))
flg = True
mn = 1 << 50
for u,x,y in infos:
    if u == "D":
        # Lの中で、yより小さくて切片がx+yのもの
        ys = lr_dic_p[dic["L"]][x+y]
        for y_ in ys:
            if y_ < y:
                flg = False
                mn = min(mn, abs(y-y_))
        # Rの中で、yより小さくて切片が-x+yのもの
        ys = lr_dic_p[dic["R"]][x-y]
        for y_ in ys:
            if y_ < y:
                flg = False
                mn = min(mn, abs(y-y_))
        # Uの中でxが一致するもの
        ys = ud_dic[dic["U"]][x]
        for y_ in ys:
            if y_ < y:
                flg = False
                mn = min(mn, abs(y-y_)/2)
    elif u == "U":
        # Lの中で、yより大きくて切片が-x+yのもの
        ys = lr_dic_p[dic["L"]][x-y]
        for y_ in ys:
            if y_ > y:
                flg = False
                mn = min(mn, abs(y-y_))
        # Rの中で、yより大きくて切片がx+yのもの
        ys = lr_dic_p[dic["R"]][x+y]
        for y_ in ys:
            if y_ > y:
                flg = False
                mn = min(mn, abs(y-y_))
        # Dのなかでxが一致するもの
        ys = ud_dic[dic["D"]][x]
        for y_ in ys:
            if y_ > y:
                flg = False
                mn = min(mn, abs(y-y_)/2)

    elif u == "R":
        # Dの中で、xより大きくて切片が-x+yのもの
        xs = ud_dic_m[dic["D"]][-x+y]
        for x_ in xs:
            if x_ > x:
                flg = False
                mn = min(mn, abs(x-x_))
        # Uの中で、xより大きくて切片がx+yのもの
        xs = ud_dic_m[dic["U"]][x+y]
        for x_ in xs:
            if x_ > x:
                flg = False
                mn = min(mn, abs(x-x_))
        # Lのなかでyが一致するもの
        xs = lr_dic[dic["L"]][y]
        for x_ in xs:
            if x_ > x:
                flg = False
                mn = min(mn, abs(x-x_)/2)

    elif u == "L":
        # Dの中で、xより小さくて切片がx+yのもの
        xs = ud_dic_m[dic["D"]][x+y]
        for x_ in xs:
            if x_ < x:
                flg = False
                mn = min(mn, abs(x-x_))
        # Uの中で、xより小さくて切片が-x+yのもの
        xs = ud_dic_m[dic["U"]][-x+y]
        for x_ in xs:
            if x_ < x:
                flg = False
                mn = min(mn, abs(x-x_))

        # Rのなかでyが一致するもの
        xs = lr_dic[dic["R"]][y]
        for x_ in xs:
            if x_ < x:
                flg = False
                mn = min(mn, abs(x-x_)/2)

if flg:
    print("SAFE")
else:
    print(int(mn*10))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict


def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    UD = defaultdict(list)
    RL = defaultdict(list)
    RD = defaultdict(list)
    UL = defaultdict(list)
    LD = defaultdict(list)
    RU = defaultdict(list)
    U = []
    D = []
    R = []
    L = []

    for i in range(N):
        x, y, d = input().split()
        x = int(x)
        y = int(y)
        if d == "U":
            UD[x].append(y)
            UL[x - y].append(y)
            U.append((x, y))
        elif d == "D":
            D.append((x, y))
        elif d == "R":
            RL[y].append(x)
            RD[x - y].append(x)
            RU[x + y].append(x)
            R.append((x, y))
        elif d == "L":
            LD[x + y].append(x)
            L.append((x, y))
    ans = 10 ** 9

    while L:
        x, y = L.pop()
        rx = RL[y]
        while rx:
            xxx = rx.pop()
            if xxx <= x:
                ans = min(ans, (x - xxx) / 0.2)

        ul = UL[x - y]
        while ul:
            yyy = ul.pop()
            if yyy >= y:
                ans = min(ans, (yyy - y) / 0.1)
    while D:
        x, y = D.pop()
        ud = UD[x]
        while ud:
            yyy = ud.pop()
            if y >= yyy:
                ans = min(ans, (y - yyy) / 0.2)

        rd = RD[x - y]
        while rd:
            xxx = rd.pop()
            if xxx <= x:
                ans = min(ans, (x - xxx) / 0.1)

        ld = LD[x + y]
        while ld:
            xxx = ld.pop()
            if xxx >= x:
                ans = min(ans, (xxx - x) / 0.1)

    while U:
        x, y = U.pop()
        ru = RU[x + y]
        while ru:
            xxx = ru.pop()
            if x >= xxx:
                ans = min(ans, (x - xxx) / 0.1)

    if ans == 10 ** 9:
        print("SAFE")
    else:
        print(int(ans))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
l = [[0,0,'U'] for _ in range(n)]
safe_cnt = 0
def safe(x,y,u):
    if u == 'U' :
        if y > 0:
            return 1
        else:
            return 0
    if u == 'D':
        if y < 0:
            return 1
        else:
            return 0
    if u == 'L':
        if x < 0:
            return 1
        else:
            return 0
    if u == 'R':
        if x > 0:
            return 1
        else:
            return 0

def move(x,y,u):
    if u == 'U':
        return x,y+1,u
    if u == 'D':
        return x,y-1,u
    if u == 'L':
        return x-1,y,u
    if u == 'R':
        return x+1,y,u
        
for i in range(n):
    l[i] = input().split()
    l[i][0] = int(l[i][0]) * 10
    l[i][1] = int(l[i][1]) * 10
    safe_cnt += safe(*l[i])
    
time = 0
res = 0
while safe_cnt < n:
    time += 1
    s = set()
    safe_cnt = 0
    for i in range(n):
        l[i] = move(*l[i])
        s.add((l[i][0], l[i][1]))
        safe_cnt += safe(*l[i])
        
    if len(s) < n:
        res = time
        break
if res > 0:
    print(res)
else:
    print('SAFE')

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[]
U,R,D,L=[],[],[],[]
for i in range(N):
  x,y,a=input().split()
  x,y=int(x),int(y)
  A.append((x,y))
  if a=='U':
    U.append((x,y))
  elif a=='R':
    R.append((x,y))
  elif a=='D':
    D.append((x,y))
  elif a=='L':
    L.append((x,y))
T=10**10
for a,b in R:
  for c,d in U:
    if a<c and b>d:
      if c-a==b-d:
        T=min(T,c-a)
for a,b in R:
  for c,d in D:
    if a<c and b<d:
      if c-a==d-b:
        T=min(T,c-a)
for a,b in L:
  for c,d in U:
    if a>c and b>d:
      if a-c==b-d:
        T=min(T,b-d)
for a,b in L:
  for c,d in D:
    if a>c and b<d:
      if a-c==d-b:
        T=min(T,d-b)
if T==10**10:
  print('SAFE')
else:
  print(T)