ICPC 2019 Asia Regional – Seoul Problem C- Islands > 문제은행 : 정보올림피아드&알고리즘

4386 : Islands

1000 ms   
512 MB   
0 회   
0 회   


There are twin islands with convex coastlines in the southern sea of the Korean Peninsula. There are n villages on the coastline in each island. All villages are numbered from 1 to n. These numbers have been randomly assigned to villages regardless of their locations. A sequence of the village numbers in clockwise direction on the coastline of an island is called a coastline sequence. Considering a village as a point, the closed polyline connecting all villages in order of a coastline sequence forms the boundary of a convex polygon.


At a meeting of village representatives from both islands, they decided to construct a road inside each island satisfying the following three conditions.


  1. Each road passes through all villages of each island exactly once.

  2. Each road is not self-intersecting.

  3. Two road sequences of both islands are same, where a road sequence is a sequence of the village numbers along the road from the start to the end.


For example, suppose that there are six villages in each island and that two coastline sequences of two islands are (1, 5, 2, 4, 6, 3) and (3, 4, 5, 2, 6, 1), respectively. Then two roads with a road sequence (3, 1, 6, 4, 5, 2) satisfy the above conditions. See the figure below. If two coastline sequences are (1, 2, 3, 4, 5) and (1, 3, 5, 2, 4), there is no road sequence which satisfies the above conditions.





Given two coastline sequences of two islands, write a program to find a road sequence satisfying the above conditions if it exists.



Your program is to read from standard input. The input starts with a line containing an integer n (5 ≤ n ≤ 100,000), where n is the number of villages in each island. The villages are numbered from 1 to n. In the following two lines, each line contains n integers which represent a coastline sequence of each island.



​Your program is to write to standard output. Print exactly one line. The line should contain n integers which represent a road sequence satisfying above conditions if it exists, otherwise -1. If there are one or more solutions, then print an arbitrary one.


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.