레이팅 미적용오늘 소들은 유난히 장난기가 넘친다! 농부 존이 하고 싶은 것은 일렬로 서 있는 소들의 사진을 찍는 것뿐인데, 사진을 찍으려는 순간마다 소들이 계속 움직인다.
구체적으로, 농부 존의 N (1 <= N <= 20,000)마리 소는 각자 고유한 정수 ID 번호를 가지고 있다. 농부 존은 배열 A[1...N]의 내용으로 표현되는 매우 특정한 순서로 일렬로 선 소들의 사진을 찍고 싶다. 여기서 A[j]는 그 순서에서 j번째 소의 ID 번호이다. 그는 소들을 이 순서로 배치하지만, 카메라 버튼을 눌러 사진을 찍기 직전에 0마리 이상의 소들의 그룹(반드시 연속된 그룹은 아님)이 줄에서 새로운 위치들로 이동한다. 더 정확히는, 0마리 이상의 소들의 그룹이 줄에서 빠져나가고, 남은 소들이 이동하여 줄에 생긴 빈틈을 메운다. 빠져나간 소들은 그다음 줄의 다른 위치들에 다시 끼어든다 (원래 있던 자리일 필요는 없다). 좌절했지만 포기하지 않은 농부 존은 다시 소들을 A의 순서대로 배치하지만, 또다시 사진을 찍기 직전에 또 다른 0마리 이상의 소들의 그룹이 줄에서 새로운 위치들로 이동한다.
위 과정은 농부 존이 포기하기 전까지 총 다섯 장의 사진에 걸쳐 반복된다. 각 사진의 내용이 주어졌을 때, 원래 의도한 순서 A를 복원할 수 있는지 보자. 각 사진은 0마리 이상의 소들의 어떤 그룹이 이동했다는 점에서 A와 다른 소들의 순서를 보여 준다. 하지만 각 소는 최대 한 장의 사진에서만 이동한다. 즉, 어떤 소가 한 사진에서 이동한 그룹에 속했다면, 나머지 네 장의 사진에서는 능동적으로 이동하지 않는다 (물론 주변의 다른 소들이 이동한 결과로 다른 인덱스에 있게 될 수는 있다).
문제 제공: Brian Dean, 2011
첫째 줄: 소의 수 N (1 <= N <= 20,000).
둘째 줄부터 5N+1번째 줄까지: 다음 5N개의 줄은 다섯 개의 순서를 나타내며, 각각은 연속된 N개의 줄로 이루어진 블록이다. 각 줄에 범위 0...1,000,000,000의 정수인 소의 ID가 주어진다.
첫째 줄부터 N번째 줄까지: 의도한 순서 A를 한 줄에 ID 하나씩 출력한다.
photo.in · 출력을 쓸 파일 photo.out5
10
20
30
40
50
20
10
30
40
50
30
10
20
40
50
40
10
20
30
50
50
10
20
30
4010
20
30
40
50Input details: There are 5 cows, with IDs 10, 20, 30, 40, and 50. In each of the 5 photos, a different cow moves to the front of the line (at most one cow moves in each photo here, but it is possible in other inputs that multiple cows could move in a particular photo).
Output details: The correct original ordering A[1..5] is 10, 20, 30, 40, 50.
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > December > Gold