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:
#root.search(x): ◯.data == x のものが存在するある場合それを出力、ない場合Noneを出力
#root.insert(x): ◯.data == xが存在する場合Falseを出力、ない場合◯.data == x なる頂点を作る
#y.to_s(): 頂点yのdataを出力
#y.left_s(): 頂点yのleftを出力(ない場合はNone)
#root.search_lower(x,None): ○.dataがxより小さいものの中で最も大きいものを出力、ない場合Noneを出力
#root.search_higher(x,None): xより大きいものの中で最も小さいものを出力、ない場合Noneを出力

################################################################################
class Avltree:
    def __init__(self,key=None):
        self.key = key
        self.left = None
        self.right = None 
        self.balance = "Even"
    def search(self,key):
        if self.key == None:
            return None
        if self.key > key:
            if self.left == None:
                return None
            else:
                return self.left.search(key)
        if self.key < key:
            if self.right == None:
                return None
            else:
                return self.right.search(key)
        return self # self.key == keyの場合
        
    def search_lower(self,key,key_lower):
        if self.key == None:
            return key_lower
        if self.key > key:
            if self.left == None:
                return key_lower
            else:
                return self.left.search_lower(key,key_lower)
        if self.key < key:
            key_lower = self.key
            if self.right == None:
                return key_lower
            else:
                return self.right.search_lower(key,key_lower)
        #self.key == keyの場合
        if self.left == None:
            return key_lower
        else:
            if key_lower == None:
                return self.left.end_higher(self.left.key)
            else:
                return max(key_lower,self.left.end_higher(self.left.key))
    
    def search_higher(self,key,key_higher):
        if self.key == None:
            return key_higher
        if self.key > key:
            key_higher = self.key
            if self.left == None:
                return key_higher
            else:
                return self.left.search_higher(key,key_higher)
        if self.key < key:
            if self.right == None:
                return key_higher
            else:
                return self.right.search_higher(key,key_higher)
        #self.key == keyの場合
        if self.right == None:
            return key_higher
        else:
            if key_higher == None:
                return self.right.end_lower(self.right.key)
            else:
                return min(key_higher,self.right.end_lower(self.right.key))
        
    
    def end_lower(self,end_lower_key):
        if self.left == None:
            return end_lower_key
        else:
            end_lower_key = self.left.key
            return self.left.end_lower(end_lower_key)
    def end_higher(self,end_higher_key):
        if self.right == None:
            return end_higher_key
        else:
            end_higher_key = self.right.key
            return self.right.end_higher(end_higher_key)
    
            
    def DoubleRightRotation(self):
        tl = self.left
        self.left = tl.right.right
        tl.right.right = self # selfはそのノード
        tlr = tl.right
        tl.right = tlr.left
        tlr.left = tl
        if tlr.balance == "Left":
            tlr.right.balance = "Right"
            tlr.left.balance = "Even"
        elif tlr.balance == "Right":
            tlr.right.balance = "Even"
            tlr.left.balance = "Left"
        elif tlr.balance == "Even":
            tlr.right.balance = "Even"
            tlr.left.balance = "Even"
        tlr.balance = "Even"
        return tlr
    def DoubleLeftRotation(self):
        tr = self.right
        self.right = tr.left.left
        tr.left.left = self
        trl = tr.left
        tr.left = trl.right
        trl.right = tr
        if trl.balance == "Right":
            trl.left.balance = "Left"
            trl.right.balance = "Even"
        elif trl.balance == "Left":
            trl.left.balance = "Even"
            trl.right.balance = "Right"
        elif trl.balance == "Even":
            trl.left.balance = "Even"
            trl.right.balance = "Even"
        trl.balance = "Even"
        return trl
    def SingleLeftRotation(self):
        tr = self.right
        tr.balance = "Even"
        self.balance = "Even"
        self.right = tr.left
        tr.left = self
        return tr
    def SingleRightRotation(self):
        tl = self.left
        tl.balance = "Even"
        self.balance = "Even"
        self.left = tl.right
        tl.right = self
        return tl
    def replace(self,p,v): # 親ノードpの下にある自分(self)をvに置き換える。
        if p.left == self:
            p.left = v
        else :
            p.right = v 
    def insert(self,key): # rootでのみ呼ばれる挿入
        if self.key == None: # rootを含むrotationはしないことにする。
            self.key = key
            return self
        if key < self.key:
            if self.left == None:
                self.left = Avltree(key)
            else:
                self.left.insertx(self,key)
        elif key > self.key:
            if self.right == None:
                self.right = Avltree(key)
            else:
                self.right.insertx(self,key)
        else: # key == self.key:
            pass # do not overwrite
    def insertx(self,p,key): # replaceを呼ぶために一つ上の親を持っているinsert
        if self.key > key:
            if self.left == None:
                self.left = Avltree(key)
            else:
                if not self.left.insertx(self, key): # 左の木が生長しなければ、
                    return False # 成長しない
            if self.balance == "Right":
                self.balance = "Even"
                return False
            elif self.balance == "Even":
                self.balance = "Left"
                return True # 成長した
            elif self.balance == "Left":
                if self.left.balance == "Right":
                    self.replace(p,self.DoubleRightRotation())
                elif self.left.balance == "Left":
                    self.replace(p,self.SingleRightRotation())
                return False # rotationを行うと成長しない
        if self.key < key:
            if self.right == None:
                self.right = Avltree(key)
            else:
                if not self.right.insertx(self, key):
                    return False 
            if self.balance == "Left":
                self.balance = "Even"
                return False
            elif self.balance == "Even":
                self.balance = "Right"
                return True
            elif self.balance == "Right":
                if self.right.balance == "Left": 
                    self.replace(p,self.DoubleLeftRotation())
                elif self.right.balance == "Right":
                    self.replace(p,self.SingleLeftRotation())
                return False
        return False # self.key == keyの時は何もしないので成長もしない 

    def to_s(self):
        return self.key
    def left_s(self):
        if self.left == None:
            return None
        return (self.left).key
    def right_s(self):
        if self.right == None:
            return None
        return (self.right).key


n = int(input())
a = [list(input().split()) for i in range(n)]
for i in range(n):
    if a[i][2] == "R":
        a[i][2] = 1
    elif a[i][2] == "L":
        a[i][2] = 2
    elif a[i][2] == "U" :
        a[i][2] = 3
    else:
        a[i][2] = 4
    a[i][0] = int(a[i][0])
    a[i][1]=int(a[i][1])
a.sort(key=lambda x: x[2])
m = 200001
R1 = [Avltree() for i in range(400002)]
R2 = [Avltree() for i in range(400002)]
L1 = [Avltree() for i in range(400002)]
L2 = [Avltree() for i in range(400002)]
U = [Avltree() for i in range(400002)]
R = [Avltree() for i in range(400002)]

M=100000000000
for x, y, u in a:
    if u == 1:
        R1[y - x + m].insert(x)
        R2[x + y].insert(x)
        R[y].insert(x)
    elif u == 2:
        L1[x + y].insert(x)
        L2[y - x + m].insert(x)
        k = R[y].search_lower(x, None)
        if k:
            M = min((k-x)/2, M)

    if u == 3:
        k = L2[y - x + m].search_higher(x, None)
        if k:
            M = min(M, k-x)
        k = R2[x + y].search_lower(x, None)
        if k:
            M = min(M, x - k)
        U[x].insert(y)
    if u == 4:
        k = L1[x + y].search_higher(x, None)
        if k:
            M = min(M, k-x)
        k = L1[y - x + m].search_lower(x, None)
        if k:
            M = min(M, x - k)
        k = U[x].search_lower(y, None)
        if k:
            M = min(M, (M-y)/2)
print(int(10*M) if M<100000000000 else "SAFE")

Submission status: Wrong Answer

Solution code:
N=int(input())
xyu=[list(input().split()) for _ in range(N)]

Us=[]
Ds=[]
Rs=[]
Ls=[]
for x, y, u in xyu:
  if u=='U':
    Us.append([int(x), int(y)])
  elif u=='D':
    Ds.append([int(x), int(y)])
  elif u=='R':
    Rs.append([int(x), int(y)])
  else:
    Ls.append([int(x), int(y)])
    
ans=float('inf')

Lsp=[[] for _ in range(400001)]
for i in range(len(Ls)):
  Lsp[Ls[i][0]+Ls[i][1]-200000].append(Ls[i])  

for Utmp in Us:
  for Ltmp in Lsp[Utmp[0]+Utmp[1]]:
    if Ltmp[0]-Utmp[0]>0:
      ans=min(ans, Ltmp[0]-Utmp[0])
      
for Dtmp in Ds:
  for Ltmp in Lsp[Dtmp[0]+Dtmp[1]]:
    if Ltmp[0]-Dtmp[0]>0:
      ans=min(ans, Ltmp[0]-Dtmp[0])
      
Rsn=[[] for _ in range(400001)]
for i in range(len(Rs)):
  Rsn[Rs[i][0]-Rs[i][1]-200000].append(Rs[i])  

for Utmp in Us:
  for Rtmp in Rsn[Utmp[0]-Utmp[1]]:
    if Rtmp[0]-Utmp[0]>0:
      ans=min(ans, Rtmp[0]-Utmp[0])
      
for Dtmp in Ds:
  for Rtmp in Rsn[Dtmp[0]-Dtmp[1]]:
    if Rtmp[0]-Dtmp[0]>0:
      ans=min(ans, Rtmp[0]-Dtmp[0])

ans*=10
Ut=[[] for _ in range(200001)]
for Utmp in Us:
  Ut[Utmp[0]].append(Utmp[1])
  
Dt=[[] for _ in range(200001)]
for Dtmp in Ds:
  Dt[Dtmp[0]].append(Dtmp[1])
  
Rt=[[] for _ in range(200001)]
for Rtmp in Rs:
  Rt[Rtmp[0]].append(Rtmp[1])
  
Lt=[[] for _ in range(200001)]
for Ltmp in Ls:
  Lt[Ltmp[0]].append(Ltmp[1])
  
import bisect

for a in range(200001):
  for b in Ut[a]:
    Dt[a].sort()
    c=bisect.bisect_left(Dt[a], b)
    if c<len(Dt[a]):
      ans=min(ans, (Dt[a][c]-b)*5)
      
for a in range(200001):
  for b in Rt[a]:
    Lt[a].sort()
    c=bisect.bisect_left(Rt[a], b)
    if c<len(Lt[a]):
      ans=min(ans, (Lt[a][c]-b)*5)
      
if ans==float('inf'):
  print('SAFE')
else:
  print(ans)

Submission status: Wrong Answer

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


ans = 200000200000200000
for x1, y1, d1 in p:
    for x2, y2, d2 in p:
        if d1==d2:
            continue
        elif (d1=='R' and d2=='L') or (d2=='R' and d1=='L'):
            if y1!=y2:
                continue
            ans = min(ans, abs(x1-x2)*5)
        elif (d1=='U' and d2=='D') or (d2=='U' and d1=='D'):
            if x1!=x2:
                continue
            ans = min(ans, abs(y1-y2)*5)
        
        elif (d1=='U' and d2=='L') or (d1=='L' and d2=='U'):
            if d1=='L':
                x1, x2 = x2, x1
                y1, y2 = y2, y1
                d1, d2 = d2, d1
            if x1>=x2 or y1>=y2 or y2-y1!=x2-x1:
                continue
            ans = min(ans, (y2-y1)*10)
        elif (d1=='U' and d2=='R') or (d1=='R' and d2=='U'):
            if d1=='R':
                x1, x2 = x2, x1
                y1, y2 = y2, y1
                d1, d2 = d2, d1
            if x2>=x1 or y1>=y2 or y2-y1!=x1-x2:
                continue
            ans = min(ans, (y2-y1)*10)
        elif (d1=='D' and d2=='L') or (d1=='L' and d2=='D'):
            if d1=='L':
                x1, x2 = x2, x1
                y1, y2 = y2, y1
                d1, d2 = d2, d1
            if y2>=y1 or x1>=x2 or y1-y2!=x2-x1:
                continue
            ans = min(ans, (y1-y2)*10)
        elif (d1=='D' and d2=='R') or (d1=='R' and d2=='D'):
            if d1=='R':
                x1, x2 = x2, x1
                y1, y2 = y2, y1
                d1, d2 = d2, d1
            if y2>=y1 or x2>=x1 or y1-y2!=x1-x2:
                continue
            ans = min(ans, (y1-y2)*10)
if ans==200000200000200000:
    print('SAFE')
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N=int(input())
P=[]
for i in range(N):
    x,y,u=map(str,input().split())
    x=int(x);y=int(y)
    P.append((x,y,u))
A=[]
B=[]
C=[]
D=[]
for i in range(N):
    A.append((P[i][0],i))
    B.append((P[i][1],i))
    C.append((P[i][0]+P[i][1],i))
    D.append((P[i][0]-P[i][1],i))
A.sort()
B.sort()
C.sort()
D.sort()
a=[p[0] for p in A]
aa=[p[1] for p in A]
b=[p[0] for p in B]
bb=[p[1] for p in B]
c=[p[0] for p in C]
cc=[p[1] for p in C]
d=[p[0] for p in D]
dd=[p[1] for p in D]
ans=10**15
for i in range(N):
    x,y,u=P[i]
    if u=="U" or u=="D":
        j=bisect.bisect_left(a,x)
        k=bisect.bisect_right(a,x)
        for l in range(j,k):
            if aa[l]==i:
                continue
            if a[l]!=x:
                break
            if P[aa[l]][2]!=u and ((u=="U" and y<P[aa[l]][1]) or (u=="D" and y>P[aa[l]][1])):
                ans=min(ans,abs(P[aa[l]][1]-y)*5)
    elif u=="R" or u=="L":
        j=bisect.bisect_left(b,y)
        k=bisect.bisect_right(b,y)
        for l in range(j,k):
            if bb[l]==i:
                continue
            if b[l]!=y:
                break
            if P[bb[l]][2]!=u and ((u=="U" and x<P[bb[l]][0]) or (u=="D" and x>P[bb[l]][0])):
               ans=min(ans,abs(P[aa[l]][1]-y)*5)
    j=bisect.bisect_left(c,x+y)
    k=bisect.bisect_right(c,x+y)
    for l in range(j,k):
        if cc[l]==i:
            continue
        if c[l]!=x+y:
            break
        X=P[cc[l]][0]
        Y=P[cc[l]][1]
        U=P[cc[l]][2]
        if u=="D" and U=="L":
            if y<Y:
                ans=min(ans,(Y-y)*10)
        if u=="L" and U=="D":
            if Y<y:
                ans=min(ans,(y-Y)*10)
        if u=="U" and U=="R":
            if Y<y:
                ans=min(ans,(y-Y)*10)
        if u=="R" and U=="U":
            if y<Y:
                ans=min(ans,(Y-y)*10)
    j=bisect.bisect_left(d,x-y)
    k=bisect.bisect_right(d,x-y)
    for l in range(j,k):
        if dd[l]==i:
            continue
        if d[l]!=x-y:
            break
        X=P[dd[l]][0]
        Y=P[dd[l]][1]
        U=P[dd[l]][2]
        if u=="U" and U=="L":
            if y<Y:
                ans=min(ans,(Y-y)*10)
        if u=="L" and U=="U":
            if Y<y:
                ans=min(ans,(y-Y)*10)
        if u=="D" and U=="R":
            if Y<y:
                ans=min(ans,(y-Y)*10)
        if u=="R" and U=="D":
            if y<Y:
                ans=min(ans,(Y-y)*10)

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import *
def solve():
  ans = float('inf')
  N = int(input())
  L_y = defaultdict(lambda: [-float('inf'),float('inf')])
  R_y = defaultdict(lambda: [-float('inf'),float('inf')])
  U_x = defaultdict(lambda: [-float('inf'),float('inf')])
  D_x = defaultdict(lambda: [-float('inf'),float('inf')])
  R_xpy = defaultdict(lambda: [-float('inf'),float('inf')])
  R_y_x = defaultdict(lambda: [-float('inf'),float('inf')])
  L_xpy = defaultdict(lambda: [-float('inf'),float('inf')])
  L_y_x = defaultdict(lambda: [-float('inf'),float('inf')])
  U_xpy = defaultdict(lambda: [-float('inf'),float('inf')])
  U_y_x = defaultdict(lambda: [-float('inf'),float('inf')])
  D_xpy = defaultdict(lambda: [-float('inf'),float('inf')])
  D_y_x = defaultdict(lambda: [-float('inf'),float('inf')])
  for i in range(N):
    x,y,u = input().split()
    x,y = int(x),int(y)
    if u=='D':
      insort(D_x[x],y)
      insort(D_xpy[x+y],x)
      insort(D_y_x[y-x],x)
    if u=='U':
      insort(U_x[x],y)
      insort(U_xpy[x+y],x)
      insort(U_y_x[y-x],x)
    if u=='L':
      insort(L_y[y],x)
      insort(L_xpy[x+y],x)
      insort(L_y_x[y-x],x)
    if u=='R':
      insort(R_y[y],x)
      insort(R_xpy[x+y],x)
      insort(R_y_x[y-x],x)
  for k,v in R_y.items():
    for zahyou in v[1:-1]:
      ind = bisect_right(L_y[k],zahyou)
      dis = L_y[k][ind]-zahyou
      ans = min(ans,dis)
  for k,v in D_x.items():
    for zahyou in v[1:-1]:
      ind = bisect_right(U_x[k],zahyou)
      dis = U_x[k][ind]-zahyou
      ans = min(ans,dis)
  for k,v in L_y_x.items():
    for zahyou in v[1:-1]:
      ind = bisect_right(U_y_x[k],zahyou)
      dis = zahyou-U_y_x[k][ind-1]
      dis *= 2
      ans = min(ans,dis)
  for k,v in R_xpy.items():
    for zahyou in v[1:-1]:
      ind = bisect_right(U_xpy[k],zahyou)
      dis = U_xpy[k][ind]-zahyou
      dis *= 2
      ans = min(ans,dis)
  for k,v in L_xpy.items():
    for zahyou in v[1:-1]:
      ind = bisect_right(D_xpy[k],zahyou)
      dis = zahyou-D_xpy[k][ind-1]
      dis *= 2
      ans = min(ans,dis)
  for k,v in R_y_x.items():
    for zahyou in v[1:-1]:
      ind = bisect_right(D_y_x[k],zahyou)
      dis = D_y_x[k][ind]-zahyou
      dis *= 2
      ans = min(ans,dis)
  ans *= 5
  return ans if ans<float('inf') else 'SAFE'
print(solve())

Submission status: Wrong Answer

Solution code:
import numpy as np
n=int(input())
A=[list(input().split()) for i in range(n)]
A_xy=[]
A_U=[]
for i in range(n):
    A_xy.append([int(A[i][0]),int(A[i][1])])
    A_U.append(A[i][2])

A_U_matrix=[]
for a in A_U:
    if a=="U": A_U_matrix.append([0,1])
    elif a=="R": A_U_matrix.append([1,0])
    elif a=="D": A_U_matrix.append([0,-1])
    elif a=="L": A_U_matrix.append([-1,0])
        
A_xy=10*np.array(A_xy)
A_U_matrix=np.array(A_U_matrix)

#print(A_xy)

ans=0
for i in range(1,20001):
    A_xy=A_xy+A_U_matrix
    if len(A_xy)!=len(np.unique(A_xy,axis=0)):
        ans=i
        break
        
#print(A_xy)
#print(np.unique(A_xy,axis=0))
#print(len(A_xy))

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

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:
import sys
from operator import itemgetter
L, U, R, D = [], [], [], []
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def sm(x):
    return x[0]+x[1]


def df(x):
    return x[0]-x[1]


N = int(input())
for _ in range(N):
    x, y, u = input().split()
    x = int(x)
    y = int(y)
    if u == "L":
        L.append((x, y))
    elif u == "R":
        R.append((x, y))
    elif u == "U":
        U.append((x, y))
    elif u == "D":
        D.append((x, y))

Rsum = sorted(R, key=lambda x: x[0]+x[1])
Rdif = sorted(R, key=lambda x: x[0]-x[1])
R = sorted(R, key=itemgetter(1))
Lsum = sorted(L, key=lambda x: x[0]+x[1])
Ldif = sorted(L, key=lambda x: x[0]-x[1])
L = sorted(L, key=itemgetter(1))
Usum = sorted(U, key=lambda x: x[0]+x[1])
Udif = sorted(U, key=lambda x: x[0]-x[1])
U = sorted(U)
Dsum = sorted(D, key=lambda x: x[0]+x[1])
Ddif = sorted(D, key=lambda x: x[0]-x[1])
D = sorted(D)


inf = 10**18
ans = inf
# RvsU
if R and U:
    i = 0
    for u in Usum:
        ux = sm(u)
        while ux != sm(Rsum[i]):
            if i < len(Rsum) - 1 and ux <= sm(Rsum[i + 1]):
                i += 1
            else:
                break
        if ux == sm(Rsum[i]) and u[0] > Rsum[i][0]:
            ans = min(ans, u[0] - Rsum[i][0])

# RvsD
if D and R:
    i = 0
    for d in Ddif:
        dx = df(d)
        while dx != df(Rdif[i]):
            if i < len(Rdif) - 1 and dx <= df(Rdif[i + 1]):
                i += 1
            else:
                break
        if dx == df(Rdif[i]) and d[0] > Rdif[i][0]:
            ans = min(ans, d[0] - Rdif[i][0])

# LvsU
if U and L:
    i = 0
    for u in Udif:
        ux = df(u)
        while ux != df(Ldif[i]):
            if i < len(Ldif) - 1 and ux <= df(Ldif[i + 1]):
                i += 1
            else:
                break
        if ux == df(Ldif[i]) and u[0] < Ldif[i][0]:
            ans = min(ans, Ldif[i][0]-u[0])

# LvsD
if L and D:
    i = 0
    for d in Dsum:
        dx = sm(d)
        while dx != sm(Lsum[i]):
            if i < len(Lsum) - 1 and dx <= sm(Lsum[i + 1]):
                i += 1
            else:
                break
        if dx == sm(Lsum[i]) and d[0] < Lsum[i][0]:
            ans = min(ans, Lsum[i][0] - d[0])

# RvsL
if R and L:
    i = 0
    for xr, yr in R:
        while yr != L[i][1]:
            if i < len(L) - 1 and yr >= L[i + 1][1]:
                i += 1
            else:
                break
        if yr == L[i][1] and xr < L[i][0]:
            ans = min(ans, (L[i][0] - xr) // 2)

# UvsD
if U and D:
    i = 0
    for xu, yu in U:
        while xu != D[i][0]:
            if i < len(D) - 1 and xu >= D[i + 1][0]:
                i += 1
            else:
                break
        if xu == D[i][0] and yu < D[i][1]:
            ans = min(ans, (D[i][1] - yu) // 2)


if ans >= inf:
    print("SAFE")
else:
    print(ans*10)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [list(input().split()) for i in range(n)]
l = 2*10**5 + 5
# l = 5
# B = [[int(A[i][0]), int(A[i][1]), int(A[i][0])+int(A[i][1]), int(A[i][0])-int(A[i][1])+l, A[i][2]] for i in range(n)]

D = [[[] for j in range(2*l)] for i in range(4)]

# for i in range(4):
#     for j in range(n):
#         D[i][B[j][i]].append(B[j])

for i in range(n):
    x = int(A[i][0])
    y = int(A[i][1])
    nn = [x,y,A[i][2]]
    D[0][x].append(nn)
    D[1][y].append(nn)
    D[2][x+y].append(nn)
    D[3][x-y+l].append(nn)

# print(D)
import bisect
ans = float("inf")
for i in range(l):
    # print(D[1][i])
    LR = [[], []]
    for j in range(len(D[1][i])):
        
        if D[1][i][j][2] == "L":
            LR[0].append(D[1][i][j][0])
        if D[1][i][j][2] == "R":
            LR[1].append(D[1][i][j][0])
    LR[0].sort()
        # print(j,LR)
    for k in range(len(LR[1])):
        ind = bisect.bisect(LR[0], LR[1][k])
        if ind != len(LR[0]):
            ans = min(ans, LR[0][ind]-LR[1][k]) * 5

for i in range(l):
    # print(D[0][i])
    LR = [[], []]
    for j in range(len(D[0][i])):
        
        if D[0][i][j][2] == "U":
            LR[0].append(D[0][i][j][1])
        if D[0][i][j][2] == "D":
            LR[1].append(D[0][i][j][1])

    LR[1].sort()
        # print(j,LR)
    for k in range(len(LR[0])):
        ind = bisect.bisect(LR[1], LR[0][k])
        # print("ind",ind)
        if ind != len(LR[1]):
            ans = min(ans, LR[1][ind]-LR[0][k]) * 5

for i in range(2*l):
    # print(D[1][i])
    LR = [[], []]
    LR2 = [[], []]
    for j in range(len(D[2][i])):
        
        if D[2][i][j][2] == "L":
            LR[0].append(D[2][i][j][0])
        if D[2][i][j][2] == "D":
            LR[1].append(D[2][i][j][0])

        if D[2][i][j][2] == "U":
            LR2[0].append(D[2][i][j][1])
        if D[2][i][j][2] == "R":
            LR2[1].append(D[2][i][j][1])
        

    # print(j,LR2)
    LR[0].sort()
    LR2[0].sort()

    for k in range(len(LR[1])):
        ind = bisect.bisect(LR[0], LR[1][k])
        if ind != len(LR[0]):
            ans = min(ans, LR[0][ind]-LR[1][k]) * 10
    
    for k in range(len(LR2[1])):
        ind = bisect.bisect(LR2[0], LR2[1][k])
        if ind != len(LR2[0]):
            ans = min(ans, LR2[0][ind]-LR2[1][k]) * 10

for i in range(2*l):
    # print(D[1][i])
    LR = [[], []]
    LR2 = [[], []]
    for j in range(len(D[3][i])):
        
        if D[3][i][j][2] == "D":
            LR[0].append(D[3][i][j][1])
        if D[3][i][j][2] == "R":
            LR[1].append(D[3][i][j][1])

        if D[3][i][j][2] == "L":
            LR2[0].append(D[3][i][j][0])
        if D[3][i][j][2] == "U":
            LR2[1].append(D[3][i][j][0])
    
    LR[0].sort()
    LR2[0].sort()

        # print(j,LR)
    for k in range(len(LR[1])):
        ind = bisect.bisect(LR[0], LR[1][k])
        if ind != len(LR[0]):
            ans = min(ans, LR[0][ind]-LR[1][k]) * 10
    
    for k in range(len(LR2[1])):
        ind = bisect.bisect(LR2[0], LR2[1][k])
        if ind != len(LR2[0]):
            ans = min(ans, LR2[0][ind]-LR2[1][k]) * 10


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

Submission status: Wrong Answer

Solution code:
n=int(input())

from collections import defaultdict

ux=set([])
uy=defaultdict(list)

dx=set([])
dy=defaultdict(list)

ry=set([])
rx=defaultdict(list)

ly=set([])
lx=defaultdict(list)

#切片
brd=set([])
brd_dic=defaultdict(list)
blu=set([])
blu_dic=defaultdict(list)
bru=set([])
bru_dic=defaultdict(list)
bld=set([])
bld_dic=defaultdict(list)

for _ in range(n):
    x,y,u=map(str,input().split())
    x=int(x)
    y=int(y)
    if u=="U":
        ux.add(x)
        uy[x].append(y)
        blu.add(y-x)
        blu_dic[y-x].append(x)
        bru.add(y+x)
        bru_dic[y+x].append(x)

    elif u=="D":
        dx.add(x)
        dy[x].append(y)
        
        bld.add(y+x)
        bld_dic[y+x].append(x)
        brd.add(y-x)
        brd_dic[y-x].append(x)
    elif u=="R":
        ry.add(y)
        rx[y].append(x)

        bru.add(y+x)
        bru_dic[y+x].append(x)
        brd.add(y-x)
        brd_dic[y-x].append(x)

    else:
        ly.add(y)
        lx[y].append(x)
        blu.add(y-x)
        blu_dic[y-x].append(x)
        bld.add(y+x)
        bld_dic[y+x].append(x)

ans=10**12
###UDをチェック
for x in ux:
    #x座標が同じだとぶつかる可能性がある
    if x in dx:
        for uy1 in uy[x]:
            for dy1 in dy[x]:
                if uy1<dy1 and (dy1-uy1)%2==0:
                    ans=min(ans,(dy1-uy1)//2)
###RLをチェック
for y in ry:
    #x座標が同じだとぶつかる可能性がある
    if y in ly:
        for rx1 in rx[y]:
            for lx1 in lx[y]:
                if rx1<lx1 and (lx1-rx1)%2==0:
                    ans=min(ans,(lx1-rx1)//2)

#####

for b in blu:
    tmp=blu_dic[b]
    for i in range(len(tmp)-1):
        for j in range(len(tmp)):
            if abs(tmp[i]-tmp[j])%2==0 and tmp[i]!=tmp[j]:
                ans=min(ans,abs(tmp[i]-tmp[j]))


for b in bld:
    tmp=bld_dic[b]
    for i in range(len(tmp)-1):
        for j in range(len(tmp)):
            if abs(tmp[i]-tmp[j])%2==0 and tmp[i]!=tmp[j]:
                ans=min(ans,abs(tmp[i]-tmp[j]))


for b in brd:
    tmp=brd_dic[b]
    for i in range(len(tmp)-1):
        for j in range(len(tmp)):
            if abs(tmp[i]-tmp[j])%2==0 and tmp[i]!=tmp[j]:
                ans=min(ans,abs(tmp[i]-tmp[j]))


for b in bld:
    tmp=bld_dic[b]
    for i in range(len(tmp)-1):
        for j in range(len(tmp)):
            if abs(tmp[i]-tmp[j])%2==0 and tmp[i]!=tmp[j]:
                ans=min(ans,abs(tmp[i]-tmp[j]))



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