C. Robot Collisions | Edu Round 109 Div.2

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)