레이팅 미적용오늘 소들은 유난히 장난기가 넘친다! 농부 존(Farmer John)은 그저 한 줄로 선 소들의 사진을 찍고 싶을 뿐인데, 소들은 존이 셔터를 누르기 직전마다 자꾸 움직인다.
구체적으로, FJ의 N마리 (1 <= N <= 20,000) 소에는 ID 번호 1...N이 붙어 있다. FJ는 배열 A[1...N]으로 표현되는 아주 특정한 순서로 소들을 한 줄로 세워 사진을 찍고 싶다. 여기서 A[j]는 그 순서에서 j번째 소의 ID 번호이다. 존은 소들을 이 순서로 배치하지만, 카메라 버튼을 눌러 사진을 찍기 직전에 최대 한 마리의 소가 줄에서 새로운 위치로 이동한다. 더 정확히는, 아무 소도 움직이지 않거나, 소 한 마리가 줄에서 자기 자리를 비우고 줄의 새로운 위치에 다시 끼어든다. 좌절했지만 포기하지 않은 FJ는 다시 소들을 A의 순서대로 배치하지만, 또다시 사진을 찍기 직전에 최대 한 마리의 소(처음에 움직인 소와는 다른 소)가 줄에서 새로운 위치로 이동한다.
위 과정은 FJ가 포기할 때까지 총 다섯 장의 사진에 걸쳐 반복된다. 각 사진의 내용이 주어질 때, 원래 의도했던 순서 A를 복원할 수 있는지 살펴보자. 각 사진은 초기 순서 A에서 시작하여 최대 한 마리의 소가 새로운 위치로 이동한 소들의 순서를 보여준다. 또한, 어떤 소가 한 사진에서 스스로 새로운 위치로 이동했다면, 그 소는 다른 어떤 사진에서도 스스로 움직이지 않는다 (물론 다른 소들이 움직인 결과로 다른 위치에 있게 될 수는 있다).
첫째 줄: 소의 수 N (1 <= N <= 20,000).
둘째 줄부터 5N+1번째 줄까지: 다음 5N개의 줄은 다섯 개의 순서를 설명하며, 각각 연속한 N개의 줄로 이루어진 블록이다. 각 줄에는 소의 ID인 1..N 범위의 정수가 주어진다.
첫째 줄부터 N번째 줄까지: 의도했던 순서 A를 한 줄에 ID 하나씩 출력한다.
photo.in · 출력을 쓸 파일 photo.out5
1
2
3
4
5
2
1
3
4
5
3
1
2
4
5
4
1
2
3
5
5
1
2
3
41
2
3
4
5Input details: There are 5 cows, with IDs 1, 2, 3, 4, and 5. In each of the 5 photos, a different cow moves to the front of the line.
Output details: The correct original ordering A[1..5] is 1,2,3,4,5.
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > December > Bronze