시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 26 | 8 | 7 | 30.435% |
상근이는 몇 년 전부터 춤에 빠져있다. 상근이는 스윙, 살사, 힙합과 같은 춤을 모두 마스터했고, 이제 새로운 춤을 만들어 보려고 한다.
상근이는 새로운 춤을 한달 후에 열리는 정인이의 결혼식에서 정인이를 위해 추려고 한다. 춤은 총 N명이 추고, 바닥에는 N개의 마크가 표시되어 있다. 마크 사이에는 화살표가 그려져 있는데, 각 마크로 향하는 화살표의 개수는 1개이다. 자기 자신으로 돌아오는 화살표가 있을 수도 있다.
결혼식이 시작할 때, 모든 사람은 처음에 서 있을 마크를 고른다. 두 사람이 한 마크 위에 서 있을 수는 없다. 그 다음, 음악이 시작되면 춤을 10초간 추다가 상근이의 신호에 맞추어 화살표를 따라 다음 마크로 이동하게 된다. 사람들은 화살표를 통해 이동할 때, 서로 충돌하지 않는다. 만약, 자기 자신을 향하는 화살표 위에 올라가 있는 사람은 그 마크 위에서 계속 춤을 추게 된다.
정인이의 결혼식으로부터 일년이 지났고, 새로운 결혼식이 다가오고 있다. 상근이는 이 결혼식에도 정인이의 결혼식 때 추었던 춤을 추려고 한다. 하지만, 작년의 마크와 화살표 배치를 찾을 수 없었다. 운이 좋게 결혼식 사진에서 춤이 시작했을 때의 사진과 끝났을 때의 사진을 찾을 수 있었다. 상근이는 신호는 총 K번 이었다. 즉, 사람들은 화살표를 향해 총 K번 이동했다.
두 사진이 주어졌을 때, 화살표를 어떻게 그려야 하는지 구하는 프로그램을 작성하시오. 상근이는 첫 사진을 기준으로 마크에 번호를 1부터 N까지 붙였다.
첫째 줄에 N과 K가 주어진다. (2 ≤ N ≤ 10,000, 1 ≤ K ≤ 109)
둘째 줄에는 공백으로 구분된 N개의 정수 ai가 주어진다. (1 ≤ ai ≤ N) ai는 춤을 추기 시작할 때 i번째 마크 위에 서 있던 사람이 춤을 끝났을 때 몇 번째 마크 위에 서 있었는지를 나타낸다. ai는 1부터 N까지 숫자가 한 번씩 나타난다.
총 K번 이동해서 입력으로 주어진 배치를 만들 수 있는 화살표를 그릴 수 없다면 "Impossible"을 출력한다. 아닌 경우에는 N개의 숫자를 출력한다. i번째 숫자는 i번 마크가 몇 번 마크와 화살표로 연결되었는지를 나타낸다.
6 2 3 4 5 6 1 2
5 6 1 2 3 4
4 2 3 4 1 2
2 3 4 1
ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2013 I번