아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

별난 전시품

시간 제한2초메모리 제한512 MB

요약
1부터 n까지의 순열에서 길이 k인 모든 구간의 역전 개수가 주어질 때, 그에 맞는 순열 하나를 복원한다.
난이도

어려움10점 중 8점

유형
구현, 그리디, 완전 탐색, 조합론
정답자
아직 제출이 없습니다

문제

최근 이상한 장치 전시회에 새 전시품이 들어왔다. 이 전시품은 11부터 nn까지의 수로 이루어진 무작위 순열을 하나 만들고, 그 순열을 훑으면서 n−k+1n - k + 1개의 수를 화면에 출력한다. 이 중 ii번째 수는 만들어진 순열의 ii번째부터 i+k−1i + k - 1번째까지 구간에 있는 역전의 개수이다.

순열 pp에서 역전이란 1≤i<j≤n1 \le i < j \le n이고 p\[i] > p\[j]\]인 모든 인덱스 쌍 i,ji, j를 말한다.

이 전시품에는 화면 외에도 손잡이 두 개가 있는데, 첫 번째 손잡이는 순열의 길이 nn을 정하고 두 번째 손잡이는 kk를 정한다. 관람객 바샤가 손잡이를 돌리자 화면에 수들이 나타났다. 이제 그는 이 이상한 장치가 어떤 순열을 만들었는지 알고 싶어 한다. 바샤를 도와주자.

입력

첫째 줄에 자연수 nn과 kk가 주어진다. (2≤n≤1052 \le n \le 10^5, 2≤k≤52 \le k \le 5, n≥kn \ge k) 둘째 줄에 장치가 화면에 출력한 n−k+1n - k + 1개의 수가 주어진다. 장치는 정상이며, 이 수들을 만들어 낼 수 있는 순열이 적어도 하나 존재한다.

출력

장치가 만든 순열을 공백으로 구분해 nn개의 수로 출력한다. 가능한 순열이 여러 개라면 아무거나 하나 출력한다.

예제1

  1. 예제 1

    입력
    3 2
    0 1
    
    예상 출력
    1 3 2