만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

대열 유지 - 2

면접 대비

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

요약
1부터 n까지의 수를 한 번씩 사용해 역순쌍이 정확히 k개인 순열을 출력하는 문제입니다.
난이도

보통10점 중 4점

유형
그리디, 배열, 구현
정답자
아직 제출이 없습니다

문제

샤토로프 시의 한 부대에서 제식 훈련이 이어지고 있다. 젊은 준위 안드레이는 이 훈련을 능숙하게 진행하고 있었는데, 상관 파벨 안드레예비치가 더 어려운 과제를 주기 시작했다.

보통 병사들은 키가 가장 작은 사람부터 순서대로 한 줄로 선다. 그러나 파벨 안드레예비치는 이것이 너무 지루하다며 다른 순서로 세우라고 지시했다. 무작위 순서는 지나치게 혼란스럽다고 판단해, 정확히 kk개의 역전이 있는 대열을 요구했다. 여기서 역전은 키가 더 큰 병사가 더 작은 병사보다 대열에서 앞에 서 있는 두 병사의 쌍을 뜻한다.

모든 병사의 키는 서로 다르며, 안드레이는 각 병사가 전체에서 키 순위로 몇 번째인지 알고 있다. 가장 작은 병사의 번호는 1이고, 가장 큰 병사의 번호는 nn이다.

예를 들어 대열 (3, 1, 2)에는 역전이 두 개 있다. 쌍 (3, 1)과 (3, 2)에서 키가 큰 병사가 작은 병사보다 앞에 서 있기 때문이다.

안드레이는 nn명의 병사를 정확히 kk개의 역전이 생기도록 세우는 프로그램을 부탁했다. 프로그램은 그런 순서를 찾아야 한다.

입력

입력 파일의 첫 번째이자 유일한 줄에는 두 정수 nn, kk(1≤n≤100,0001 \le n \le 100,000)가 주어진다. nn은 대열에 서는 병사의 수이고, kk는 요구되는 역전의 수이다.

정확히 kk개의 역전을 갖는 대열이 존재함이 보장된다. 즉 0≤k≤n(n−1)20 \le k \le \frac{n (n - 1)}{2}이다.

출력

요구된 순서로 세운 병사들의 번호를 정수 nn개로 출력한다.

예제2

  1. 예제 1

    입력
    3 2
    
    예상 출력
    3 1 2
    
  2. 예제 2

    입력
    3 0
    
    예상 출력
    1 2 3