시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB48151435.897%

문제

직교좌표로 이루어진 평면 위에 터널이 그려져있다.

터널의 천장은 (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개를 왼쪽부터 오른쪽으로 출력한다.

최단경로는 유일하지 않을 수도 있지만 항상 존재한다.

예제 입력 1

9
1 4 4 4 4 4 4 4 1
-1 -1 -1 -1 2 -1 -1 -1 -1

예제 출력 1

0 0 0 3 3 3 0 0 0

예제 입력 2

9
1 1 1 0 -1 0 1 1 1
-1 -4 -4 -4 -4 -4 -4 -4 -1

예제 출력 2

0 0 -1 -2 -2 -2 -1 0 0

예제 입력 3

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

예제 출력 3

0 0 -1 -1 -1 0 1 1 1 -1 -1 -1 0 0
W3sicHJvYmxlbV9pZCI6IjMxNTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQxMzBcdWIxMTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzljMVx1YWQ1MFx1Yzg4Y1x1ZDQ1Y1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVkM2M5XHViYTc0IFx1YzcwNFx1YzVkMCBcdWQxMzBcdWIxMTBcdWM3NzQgXHVhZGY4XHViODI0XHVjODM4XHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQxMzBcdWIxMTBcdWM3NTggXHVjYzljXHVjN2E1XHVjNzQwICgwLDEpXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU3NCAoTiwxKVx1YzVkMFx1YzExYyBcdWIwNWRcdWIwOWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDEzMFx1YjExMFx1Yzc1OCBcdWJjMTRcdWIyZTVcdWM3NDAgKDAsLTEpXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU3NCAoTiwtMSlcdWM1ZDBcdWMxMWMgXHViMDVkXHViMDljXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQxMzBcdWIxMTBcdWM3NDQgXHVkMWI1XHVhY2ZjXHVkNTU4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1YjI5NCAoMCwwKVx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NzQgKE4sMClcdWM1ZDBcdWMxMWMgXHViMDVkXHViMDljXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjOWNcdWM3YTUsIFx1YmMxNFx1YjJlNSwgXHVhY2JkXHViODVjXHViMjk0IFx1YmFhOFx1YjQ1MCB4XHVjZDk1IFx1YjYxMFx1YjI5NCB5XHVjZDk1XHVjNWQwIFx1ZDNjOVx1ZDU4OVx1ZDU1YyBcdWMxMjBcdWJkODRcdWM3NzQgXHVjNzc0XHVjNWI0XHVjOWM0IFx1ZDYxNVx1ZDBkY1x1Yzc3NFx1YmE3MCwgXHViYWE4XHViNGUwIFx1Y2Y1NFx1YjEwOFx1YjI5NCBcdWM4MTVcdWMyMTggXHVjODhjXHVkNDVjXHVjNzc0XHVhY2UwLCBcdWIyZTRcdWM3NGMgXHVjMTIwXHViZDg0XHVjNzU4IHhcdWM4OGNcdWQ0NWNcdWIyOTQgXHVjNzc0XHVjODA0IFx1YzEyMFx1YmQ4NFx1Yzc1OCB4XHVjMTIwXHViZDg0XHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2M5Y1x1YzdhNVx1YWNmYyBcdWJjMTRcdWIyZTVcdWM3NTggeVx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWFjMDFcdWFjMDEgLTEwMDBcdWM1ZDBcdWMxMWMgMTAwMFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNiZFx1Yjg1Y1x1YjI5NCBcdWNjOWNcdWM3YTVcdWM3NzRcdWIwOTggXHViYzE0XHViMmU1XHVhY2ZjIFx1YjJmZlx1YzU0NFx1YzExY1x1YjI5NCBcdWM1NDhcdWI0MThcdWJhNzAsIFx1Y2Y1NFx1YjEwOFx1YzVkMFx1YzExY1x1YjNjNCBcdWNjOWNcdWM3YTVcdWM3NzRcdWIwOTggXHViYzE0XHViMmU1XHVhY2ZjIFx1YjJmZlx1YzU0NFx1YzExY1x1YjI5NCBcdWM1NDggXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2NmZmFiN2I5LTM5MzAtNDBlYy1hM2UyLTE4ODg4YThlYzlkYlwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMzgwcHg7IGhlaWdodDogMTcwcHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1ZDEzMFx1YjExMFx1Yzc1OCBcdWM2MDhcdWM4MWNcdWIyOTQgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWIyZTQuIFx1Y2M5Y1x1YzdhNVx1YWNmYyBcdWJjMTRcdWIyZTVcdWM3NDAgXHVjMmU0XHVjMTIwXHVjNzNjXHViODVjLCBcdWFjYmRcdWI4NWNcdWIyOTQgXHVjODEwXHVjMTIwXHVjNzNjXHViODVjIFx1YWRmOFx1YjgyNFx1YzgzOFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMTMwXHViMTEwXHVjNzQ0IFx1ZDFiNVx1YWNmY1x1ZDU1OFx1YjI5NCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHViOTdjIFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDEzMFx1YjExMFx1Yzc1OCBcdWIxMDhcdWJlNDQgTigxICZsZTsgTiAmbGU7IDEwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjYzljXHVjN2E1XHVjNzU4IHlcdWM4OGNcdWQ0NWNcdWFjMDAgTlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjNjdjXHVjYWJkXHViZDgwXHVkMTMwIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEzOCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmMxNFx1YjJlNVx1Yzc1OCB5XHVjODhjXHVkNDVjXHVhYzAwIE5cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1YzY3Y1x1Y2FiZFx1YmQ4MFx1ZDEzMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2Q5Y1x1YjgyNVx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjYmRcdWI4NWNcdWM3NTggeVx1Yzg4Y1x1ZDQ1YyBOXHVhYzFjXHViOTdjIFx1YzY3Y1x1Y2FiZFx1YmQ4MFx1ZDEzMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNkNWNcdWIyZThcdWFjYmRcdWI4NWNcdWIyOTQgXHVjNzIwXHVjNzdjXHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHVjOWMwXHViOWNjIFx1ZDU2ZFx1YzBjMSBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzE1NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6InR1bmVsIiwiZGVzY3JpcHRpb24iOiI8cD5BIHR1bm5lbCBpcyBkcmF3biBpbiB0aGUgcmVjdGFuZ3VsYXIgY29vcmRpbmF0ZSBzeXN0ZW0uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBjZWlsaW5nIG9mIHRoZSB0dW5uZWwgc3RhcnRzIGluICgwLDEpIGFuZCBlbmRzIGluIChOLDEpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZmxvb3Igb2YgdGhlIHR1bm5lbCBzdGFydHMgaW4gKDAsLTEpIGFuZCBlbmRzIGluIChOLC0xKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHBhdGggdGhyb3VnaCB0aGUgdHVubmVsIHN0YXJ0cyBpbiAoMCwwKSBhbmQgZW5kcyBpbiAoTiwwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGNlaWxpbmcsIGZsb29yIGFuZCBwYXRoIGFyZSBzZXF1ZW5jZXMgb2YgaG9yaXpvbnRhbCBhbmQgdmVydGljYWwgc2VnbWVudHMgc3VjaCB0aGF0IGVhY2ggY29ybmVyIGhhcyBpbnRlZ2VyIGNvb3JkaW5hdGVzLCBhbmQgdGhlIHgtY29vcmRpbmF0ZSBvZiBlYWNoIGNvcm5lciBpcyBncmVhdGVyIHRoYW4gb3IgZXF1YWwgdG8gdGhlIHgtY29vcmRpbmF0ZSBvZiB0aGUgcHJldmlvdXMgY29ybmVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BbGwgb2YgdGhlIHktY29vcmRpbmF0ZXMgb2YgdGhlIGNlaWxpbmcgYW5kIHRoZSBmbG9vciB3aWxsIGJlIGludGVnZXJzIGJldHdlZW4gLTEwMDAgYW5kIDEwMDAsIGluY2x1c2l2ZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHBhdGggbXVzdCBub3QgdG91Y2ggdGhlIGNlaWxpbmcgb3IgdGhlIGZsb29yIG9mIHRoZSB0dW5uZWwsIGV2ZW4gb24gY29ybmVycy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHR1bm5lbCBmcm9tIHRoZSB0aGlyZCBleGFtcGxlIGlzIGdpdmVuIGluIHRoZSBmaWd1cmUgYmVsb3cuIFRoZSBjZWlsaW5nIGFuZCB0aGUgZmxvb3IgYXJlIHJlcHJlc2VudGVkIHdpdGggc29saWQgbGluZXMgYW5kIHRoZSBwYXRoIGlzIHJlcHJlc2VudGVkIHdpdGggdGhlIGRhc2hlZCBsaW5lLiZuYnNwOzxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2NmZmFiN2I5LTM5MzAtNDBlYy1hM2UyLTE4ODg4YThlYzlkYlwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMzgwcHg7IGhlaWdodDogMTcwcHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGZpbmRzIHNvbWUgc2hvcnRlc3QgcGF0aCB0aHJvdWdoIHRoZSB0dW5uZWwuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIE4sIDEgJmxlOyBOICZsZTsgMTAwLDAwMCwgdGhlIHdpZHRoIG9mIHRoZSB0dW5uZWwuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyBOIGludGVnZXJzICZuZGFzaDsgeS1jb29yZGluYXRlcyBvZiB0aGUgaG9yaXpvbnRhbCBzZWdtZW50cyBvZiB0aGUgY2VpbGluZywgZnJvbSBsZWZ0IHRvIHJpZ2h0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdGhpcmQgbGluZSBjb250YWlucyBOIGludGVnZXJzICZuZGFzaDsgeS1jb29yZGluYXRlcyBvZiB0aGUgaG9yaXpvbnRhbCBzZWdtZW50cyBvZiB0aGUgZmxvb3IsIGZyb20gbGVmdCB0byByaWdodC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gTiBpbnRlZ2VycyAmbmRhc2g7IHktY29vcmRpbmF0ZXMgb2YgdGhlIGhvcml6b250YWwgc2VnbWVudHMgb2YgdGhlIHBhdGgsIGZyb20gbGVmdCB0byByaWdodC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm90ZTogdGhlIHRlc3QgZGF0YSB3aWxsIGJlIHN1Y2ggdGhhdCBhIHNvbHV0aW9uLCBhbHRob3VnaCBub3QgbmVjZXNzYXJpbHkgdW5pcXVlLCBhbHdheXMgZXhpc3RzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2006 > Regional Competition - Juniors 3번

  • 문제를 다시 작성한 사람: jh05013
  • 문제를 번역한 사람: waylight3