시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 30 10 8 53.333%

문제

길이가 $N$인 수열이 있다. 이 수열은 같은 수를 여러 개 포함할 수 있고 모든 수는 $N$ 이하의 자연수이다.

이 수열을 길이가 0이 아닌 두 부분으로 나누어서 두 부분 각각 순서를 반대로 한 뒤 다시 이어 붙이려고 한다. 이렇게 해서 생성되는 모든 수열들을 나열하고 싶어하는 jhnah917은 당신에게 사전순으로 나열할 경우 어떤 수열이 $K$번째에 오게 될 것인지 물어보았다. 사전순이라 하는 것은 첫 번째 수가 작은 것이 먼저 오고, 첫 번째 수가 같다면 두 번째 수가 작은 것이 먼저 오고, 두 번째 수도 같다면 세 번째 수가…….

jhnah917이 당신에게 물어본, 위 규칙으로 생성되는 수열을 사전 순으로 나열했을 때 $K$번째로 나오는 수열을 출력하는 프로그램을 작성하여라.

입력

첫째 줄에 양의 정수 $N, K$가 주어진다. ($1 \leq K < N \leq 200\,000$)

둘째 줄에는 수열을 이루는 N개의 수가 빈 칸을 사이에 두고 차례대로 주어진다.

출력

첫째 줄에 사전순으로 나열했을 때 $K$번째로 나오는 수열을 출력하여라.

예제 입력 1

10 1
2 1 3 1 2 1 3 1 3 1

예제 출력 1

1 2 1 3 1 2 1 3 1 3

만들 수 있는 수열은 다음과 같다.

  • 1 2 1 3 1 2 1 3 1 3 (6 / 4로 분할한 경우)
  • 1 2 1 3 1 3 1 2 1 3 (2 / 8로 분할한 경우)
  • 1 3 1 2 1 3 1 2 1 3 (8 / 2로 분할한 경우)
  • 1 3 1 2 1 3 1 3 1 2 (4 / 6으로 분할한 경우)
  • 2 1 3 1 2 1 3 1 3 1 (5 / 5로 분할한 경우)
  • 2 1 3 1 3 1 2 1 3 1 (1 / 9로 분할한 경우)
  • 3 1 2 1 3 1 2 1 3 1 (7 / 3으로 분할한 경우)
  • 3 1 2 1 3 1 3 1 2 1 (3 / 7로 분할한 경우)
  • 3 1 3 1 2 1 3 1 2 1 (9 / 1로 분할한 경우)

힌트

https://www.acmicpc.net/problem/15492 을 풀어보면 도움이 될 수도 있다.

출처