시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 75 | 32 | 30 | 46.875% |
직교좌표로 이루어진 평면 위에 터널이 그려져있다.
터널의 천장은 (0,1)에서 시작해 (N,1)에서 끝난다.
터널의 바닥은 (0,-1)에서 시작해 (N,-1)에서 끝난다.
터널을 통과하는 경로는 (0,0)에서 시작해 (N,0)에서 끝난다.
천장, 바닥, 경로는 모두 x축 또는 y축에 평행한 선분이 이어진 형태이며, 모든 코너는 정수 좌표이고, 다음 선분의 x좌표는 이전 선분의 x선분보다 크거나 같다.
천장과 바닥의 y좌표는 각각 -1000에서 1000사이의 정수이다.
경로는 천장이나 바닥과 닿아서는 안되며, 코너에서도 천장이나 바닥과 닿아서는 안 된다.
터널의 예제는 주어진 그림과 같다. 천장과 바닥은 실선으로, 경로는 점선으로 그려져있다.
터널을 통과하는 최단 경로를 찾는 프로그램을 작성하시오.
입력의 첫 번째 줄에는 터널의 너비 N(1 ≤ N ≤ 100,000)이 주어진다.
두 번째 줄에는 천장의 y좌표가 N개의 정수로 왼쪽부터 오른쪽으로 주어진다.
세 번째 줄에는 바닥의 y좌표가 N개의 정수로 왼쪽부터 오른쪽으로 주어진다.
출력의 첫 번째 줄에 경로의 y좌표 N개를 왼쪽부터 오른쪽으로 출력한다.
최단경로는 유일하지 않을 수도 있지만 항상 존재한다.
9 1 4 4 4 4 4 4 4 1 -1 -1 -1 -1 2 -1 -1 -1 -1
0 0 0 3 3 3 0 0 0
9 1 1 1 0 -1 0 1 1 1 -1 -4 -4 -4 -4 -4 -4 -4 -1
0 0 -1 -2 -2 -2 -1 0 0
14 1 2 2 0 1 3 3 3 3 2 0 2 2 1 -1 -2 -2 -3 -3 -3 -1 0 -2 -3 -3 -3 -2 -1
0 0 -1 -1 -1 0 1 1 1 -1 -1 -1 0 0