링고와 순열
면접 대비시간 제한1초메모리 제한256 MB
N과 K가 주어질 때 역전 횟수가 정확히 K인 1부터 N까지의 순열을 하나 만들거나, 불가능하면 -1을 출력한다.
문제
링고는 1 이상 N 이하의 정수가 한 번씩 모두 등장하는 길이 N의 순열 [p1, p2, ..., pN]을 좋아한다.
그중에서 반전의 개수가 K인 순열을 가장 좋아한다.
순열에서 반전이란 i < j이면서 pi > pj를 만족하는 (i, j) 쌍을 말한다.
예를 들어 순열 [3, 1, 4, 5, 2]는 길이가 5이고 반전의 개수는 4개 {(1, 2), (1, 5), (3, 5), (4, 5)}이다.
링고가 가장 좋아하는 순열을 하나 찾아주자.
입력
첫 번째 줄에 N과 K (1 ≤ N ≤ 314,159, 0 ≤ K ≤ N×(N-1)/2)가 공백을 두고 주어진다.
출력
첫 번째 줄에 문제의 조건을 만족하는 p1, p2, ..., pN을 공백을 사이에 두고 출력한다.
그러한 순열이 존재하지 않으면 첫 번째 줄에 -1 하나만 출력하고 더 이상 아무것도 출력하지 않는다.
그러한 순열이 여러 가지라면 그중 하나만 출력한다.