소 사진 촬영

오늘 소들은 유난히 장난기가 넘친다! 농부 존(Farmer John)은 그저 한 줄로 선 소들의 사진을 찍고 싶을 뿐인데, 소들은 존이 셔터를 누르기 직전마다 자꾸 움직인다.

구체적으로, FJ의 N마리 (1 <= N <= 20,000) 소는 각자 고유한 정수 ID 번호를 가진다. FJ는 배열 A[1...N]으로 표현되는 아주 특정한 순서로 소들을 한 줄로 세워 사진을 찍고 싶다. 여기서 A[j]는 그 순서에서 j번째 소의 ID 번호이다. 존은 소들을 이 순서로 배치하지만, 카메라 버튼을 눌러 사진을 찍기 직전에 0마리 이상의 소로 이루어진 무리(반드시 연속한 무리일 필요는 없다)가 줄에서 새로운 위치들로 이동한다. 더 정확히는, 0마리 이상의 소 무리가 줄에서 빠져나가고, 남은 소들이 줄의 빈틈을 메우도록 이동한다. 빠져나간 소들은 그 뒤 줄의 다른 위치들에 다시 끼어든다 (원래 있던 자리일 필요는 없다). 좌절했지만 포기하지 않은 FJ는 다시 소들을 A의 순서대로 배치하지만, 또다시 사진을 찍기 직전에 (이전과 다른) 0마리 이상의 소 무리가 줄에서 새로운 위치들로 이동한다.

위 과정은 FJ가 포기할 때까지 총 다섯 장의 사진에 걸쳐 반복된다. 각 사진의 내용이 주어질 때, 원래 의도했던 순서 A를 복원할 수 있는지 살펴보자. 각 사진은 0마리 이상의 소 무리가 이동했다는 점에서 A와 다른 소들의 순서를 보여준다. 다만 한 소는 최대 한 장의 사진에서만 움직인다. 어떤 소가 한 사진에서 움직인 무리에 속했다면, 그 소는 나머지 네 사진에서는 스스로 움직이지 않는다 (물론 주변의 다른 소들이 움직인 결과로 다른 위치에 있게 될 수는 있다).

(이 문제는 USACO 2011년 12월 대회 실버 및 골드 1번 문제로 동일하게 출제되었다.)

첫째 줄: 소의 수 N (1 <= N <= 20,000).

둘째 줄부터 5N+1번째 줄까지: 다음 5N개의 줄은 다섯 개의 순서를 설명하며, 각각 연속한 N개의 줄로 이루어진 블록이다. 각 줄에는 소의 ID인 0...1,000,000,000 범위의 정수가 주어진다.

첫째 줄부터 N번째 줄까지: 의도했던 순서 A를 한 줄에 ID 하나씩 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2011-2012 > December > Silver