레이팅 미적용설명
베시는 심심해서 또다시 농부 존의 헛간에서 말썽을 부리고 있다. FJ에게는 \(N\) (\(1\leq N \leq 10^5\))개의 건초 더미 무더기가 있다. 각 \(i\in [1,N]\)에 대해, \(i\)번째 무더기에는 \(h_i\) (\(1\le h_i\le 10^9\))개의 건초 더미가 있다. 베시는 건초 더미가 무너지는 것을 원하지 않으므로, 그녀가 할 수 있는 연산은 다음뿐이다.
- 인접한 두 무더기의 높이 차가 \(K\) (\(1\le K\le 10^9\)) 이하이면, 두 무더기를 서로 맞바꿀 수 있다.
이러한 연산을 몇 번 수행한 후 베시가 얻을 수 있는 사전순으로 가장 앞서는 높이 수열은 무엇인가?
*참고: 이 문제의 시간 제한과 메모리 제한은 4초와 512MB로, 기본값의 두 배이다.*
출제자: Daniel Zhang, Benjamin Qi
제약
배점
- 전체 입력의 10%에서 \(N\le 100\)
- 다른 20%의 입력에서 \(N\le 5000\)
- 나머지 70%의 입력에는 추가 제약이 없다.
출제자: Daniel Zhang, Benjamin Qi
입력 형식
첫째 줄에 \(N\)과 \(K\)가 주어진다. \(i+1\)번째 줄에 \(i\)번째 건초 더미 무더기의 높이가 주어진다.
출력 형식
\(N\)개의 줄을 출력하며, \(i\)번째 줄에는 답에서 \(i\)번째 건초 더미 무더기의 높이를 출력한다.
예제 1
입력
5 3
7
7
3
6
2출력
6
7
7
2
3설명
One way that Bessie can swap the stacks is as follows:
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
문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > January > Platinum
태그