Placeholder

#5335

건초 더미 옮기기 (Minimizing Haybales) 4초 512MB

문제

배씨에게 N(1≤N≤105)개의 건초 더미가 있는데, 각 i∈[1, N]번째 건초 더미는 hi(1≤hi≤109)의 높이를 가지고 있다.

배씨는 인접한 두 건초 더미의 높이가 최대 K(1≤K≤109)이하 차이가 나는 경우 두 건초 더미를 교환할 수 있다.

배씨가 이러한 일련의 교환 작업을 수행한 후 얻을 수 있는 사전순 최소 수열(lexicographically minimum sequence)를 출력하자.

사전순 최소 수열​은 구할 수 있는 모든 수열 중 가장 사전순으로 정렬된 형태의 수열이다.


입력

첫 번째 줄에는 N과 K가 입력된다. 

두 번째 줄부터 N줄에 걸쳐 i+1 번째 줄에는 i 번째 건초 더미의 높이가 입력된다.


출력

i 번째 건초 더미의 높이를 i 번째 줄에 출력하시오.


예제1

입력
5 3

7
7
3
6
2
출력
6

7
7
2
3

배씨가 건초 더미를 교환할 수 있는 한 가지 방법은 다음과 같습니다.

 

   7 7 3 6 2

-> 7 7 6 3 2

-> 7 7 6 2 3

-> 7 6 7 2 3

-> 6 7 7 2 3​ 


출처

USACO 2022 January Platinum


역링크 공식 문제집만

로그인해야 코드를 작성할 수 있어요.