BOJ 2136 개미

https://www.acmicpc.net/problem/2136
시간 2초, 메모리 128MB

input :

• N L(2 ≤ L ≤ 1,000,000,000)(1 ≤ N ≤ 100,000)
• pos (0 < pos < L)

output :

• i t
• i는 가장 마지막에 떨어지는 개미의 번호
• t는 가장 마지막에 떨어지는 개미가 바닥에 떨어지는 시간

조건 :

• 개미의 번호는 입력에서 주어지는 순서대로 1, 2, …, N이다.

• 각각의 개미는 왼쪽, 혹은 오른쪽으로 움직이고 있다

• 모든 개미들은 똑같은 속도로, 1초에 한 칸씩 움직인다.

• 두 마리의 개미가 서로 부딪혔을 때, 두 마리의 개미는 모두 즉시 방향을 바꾸어 다시 움직이게 된다.

• 개미들이 이동하다가 0인 위치나 L인 위치에 도달하게 되면, 그 개미는 막대기 아래로 떨어지게 된다.

---

연관 문제

BOJ 3163 떨어지는 개미

위의 문제와 동일한 문제이다.
그러나 위치가 증가하는 순서가 아니기 때문에 이에 대한 정렬이 수행되어야 함.

출력 조건 : "가장 마지막에 떨어지는 개미가 여러 마리인 경우는 없다고 가정한다."이로 인해 2마리가 동시에 떨어지는 경우는 없다.

import sys

n, l = map(int, sys.stdin.readline().split())
ids, left, right = [], [], []

for i in range(n):
    pos = int(sys.stdin.readline())

    ids.append((abs(pos), i + 1))
    if pos > 0:
        right.append(l - pos)
    else:
        left.append(-pos)

ids.sort()
left.sort()
right.sort(reverse=True)

move = left + right
ans = [(move[i], ids[i][1]) for i in range(n)]

ans.sort()
print(ans[-1][1], ans[-1][0])