https://codeforces.com/contest/1525/problem/C
시간 2초, 메모리 256MB
input :
- t (1 ≤ t ≤ 1000)
- n m (1 ≤ n ≤ 3⋅105; 2 ≤ m ≤ 108)
- x1, x2, …, xn (0 < xi < m)
- n space-separated characters 'L' or 'R'
output :
- For each testcase print n integers — for the
i-th robot output the time it explodes at if it does and −1 otherwise.
i번째 로봇이 폭발하는 시간을 출력하시오. 폭발이 발생하지 않은 로봇의 경우 -1을 출력하시오.
조건 :
-
There are also two walls: one is at coordinate 0 and one is at coordinate m.
0과 m에는 벽이 위치합니다 -
The i-th robot starts at an integer coordinate xi (0<xi<m) and moves either left (towards the 0) or right with the speed of 1 unit per second. No two robots start at the same coordinate.
i번째 로봇은 xi에 위치하고 왼쪽 혹은 오른쪽으로 1초에 1칸씩 이동합니다. 같은 위치에서 시작하는 로봇은 존재하지 않습니다.
문제를 볼 때 이동하는 로봇들을 보면 거리이 차가 짝수인 놈들이 부딪힐 수 있다. 그런데 이걸 이렇게 보지 말고 인덱스의 위치로 보는 방법이 존재한다. 다시 말해 홀수는 홀수끼리 부딪히고 짝수는 짝수끼리 부딪히는 것이다. 그렇기 때문에 이 둘을 나눠서 생각할 수 있다.
폭발
폭발이 일어나는 로봇들은 어떤 것들인가
1. 방향 'R'인 놈이 스택의 제일 위에 있고 'L'인 놈이 들어 올 때.
2. 방향 'L'인 놈이 스택의 제일 위 'L'인 놈이 들어 올 때
일단 맨 처음에는 'L'이 들어 올 떄 삭제를 해야한다. 괄호 문제처럼 'R'을 여는 괄호 'L'을 닫는 괄호라고 볼 수 있다.
그리고 얘네들이 터지는 시간은 거리 차를 2로 나눈 값이다.
여기서 봐야 할 부분은 'L'이 스택의 탑일 때 삭제하는 방식이다. 'L' 다음에 'L'이 나온다는 의미는 벽에 반사된 이후에 폭발이 발생한 다는 의미이다.
그리고 이걸 그냥 한 번에 해결하고 싶은 것이고.
왼쪽으로 반사
왼쪽으로 계속 이동해서 다시 반대로 이동하는 것을 무엇과 동일하다고 볼 수 있을까.
거울을 생각해보자
어차피 튕기고 나와서 이동을 해서 만나는 것이다. 그렇기에 거울 반대편의 위치에 있다고 생각하고 계산을 할 수 있는것이다...
0에서 시작되기 때문에 -위치 를 하는것 만으로 거울로 볼 수 있는 위치를 찾을 수 있다.
오른쪽으로 반사
오른쪽으로 반사는 그러면 n을 기준으로 거울을 만드는 것이다. 그 위치를 구하려면 m + (m - pos)이기에 이러한 연산을 해주는 것이다.
그리고 더 오른쪽에 위치한 놈을 거울에 보이는 위치로 보낸 다면
그 이후에 pop해서 나오는 놈은 신경쓰지 않아도 된다.
홀, 짝
홀수와 짝수로 구분하기 때문에 시각적으로 더 편하게 하기 위해서 하나의 배열을 만들고 2차원 배열로써 사용한다.
import sys
def check(arr):
arr.sort(key=lambda x:x[1])
stack = []
for idx, pos, way in arr:
if way == 'L':
if not stack:
# anyway if we still have 'L' then it will work as 'R'
# so swap it.
stack.append((idx, -pos))
else:
temp = stack.pop()
ans[idx] = ans[temp[0]] = (pos - temp[1]) // 2
else:
stack.append((idx, pos))
while len(stack) > 1:
fir = stack.pop()
sec = stack.pop()
ans[fir[0]] = ans[sec[0]] = (m + m - fir[1] - sec[1]) // 2
t = int(sys.stdin.readline())
for i in range(t):
n, m = map(int, sys.stdin.readline().split())
start = list(map(int, sys.stdin.readline().split()))
direction = list(sys.stdin.readline().split())
data = [[], []]
ans = [-1] * (len(start))
for j in range(len(start)):
data[start[j] % 2].append((j, start[j], direction[j]))
check(data[0])
check(data[1])
print(*ans)
