6035 : 행성 충돌
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
일직선 상에 $N$개의 행성이 배치되어 있고 각각의 질량과 이동 방향이 주어집니다.
정수의 절댓값은 행성의 크기(질량)를 나타내며, 부호는 이동 방향을 의미합니다 (양수는 오른쪽, 음수는 왼쪽). 모든 행성은 같은 속도로 움직입니다.
두 행성이 서로 다른 방향으로 움직이다가 충돌하는 경우, 크기가 더 큰 행성은 살아남고 작은 행성은 파괴(소멸)됩니다. 만약 크기가 같다면 두 행성 모두 소멸합니다.
충돌이 모두 발생하여 상황이 종료되었을 때, 최종적으로 생존한 행성들의 목록을 구하십시오.
[제약 조건]
• 행성 수 $N$: $1 \le N \le 100{,}000$ (정수)
• 양수는 오른쪽, 음수는 왼쪽 방향이며 절댓값이 질량입니다.
정수의 절댓값은 행성의 크기(질량)를 나타내며, 부호는 이동 방향을 의미합니다 (양수는 오른쪽, 음수는 왼쪽). 모든 행성은 같은 속도로 움직입니다.
두 행성이 서로 다른 방향으로 움직이다가 충돌하는 경우, 크기가 더 큰 행성은 살아남고 작은 행성은 파괴(소멸)됩니다. 만약 크기가 같다면 두 행성 모두 소멸합니다.
충돌이 모두 발생하여 상황이 종료되었을 때, 최종적으로 생존한 행성들의 목록을 구하십시오.
[제약 조건]
• 행성 수 $N$: $1 \le N \le 100{,}000$ (정수)
• 양수는 오른쪽, 음수는 왼쪽 방향이며 절댓값이 질량입니다.
입력 설명
첫째 줄에 행성의 개수 $N$이 주어집니다. ($1 \le N \le 100,000$)
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다. (각 행성의 질량과 방향 정보)
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다. (각 행성의 질량과 방향 정보)
출력 설명
모든 충돌이 끝난 후 살아남은 행성들의 목록을 공백으로 구분하여 출력합니다. 만약 살아남은 행성이 없다면 빈 줄을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
5 10 -5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
5 10도움
스택에 행성들을 차례로 push합니다. 음수 행성(왼쪽 이동)을 만났을 때, 스택 top에 양수 행성(오른쪽 이동)이 있다면 두 행성의 절댓값 크기를 비교하며 pop 처리를 반복합니다.