/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
整数 N, K が与えられます.
長さ N の整数列 X=(X_1,X_2,\dots ,X_N) の累積和とは, 次のように定まる長さ N+1 の数列 Y=(Y_0,Y_1,\dots ,Y_N) のことです.
- Y_0=0
- Y_i=\displaystyle\sum_{j=1}^{i}X_j\ (i=1,2,\dots ,N)
長さ N の整数列 X=(X_1,X_2,\dots ,X_N) が良い数列であるとは, 次の条件を満たすことを言います.
- X の累積和の要素の任意の K 未満の値は, 任意の K 以上の値よりも前に現れる.
- 正確には, X の累積和を Y として, 0\le i,j\le N なる任意の整数組 (i,j) について, (Y_i\lt K かつ Y_j\ge K) ならば i\lt j が成り立つ.
長さ N の整数列 A=(A_1,A_2,\dots ,A_N) が与えられます. A の要素を自由に並べ替えることで A を良い数列にできるかどうか判定し, できる場合は並べ替えた後の A としてあり得るものをひとつ出力してください.
制約
- 1 \leq N \leq 2\times 10^5
- -10^9 \leq K \leq 10^9
- -10^9 \leq A_i \leq 10^9
- 入力される値はすべて整数.
入力
入力は以下の形式で標準入力から与えられる．
N K A_1 A_2 \cdots A_N
出力
A の要素を自由に並べ替えることで A を良い数列にできる場合は, 並べ替えた後の A を (A^{\prime}_1,A^{\prime}_2,\dots ,A^{\prime}_N) として, 次の形式で出力せよ.
Yes
A^{\prime}_1 A^{\prime}_2 \cdots A^{\prime}_N
なお, 条件を満たす並べ替えが複数存在する場合は, どれを出力しても正答となる.
良い数列にできない場合は No を出力せよ.
入力例 1
4 1 -1 2 -3 4
出力例 1
Yes -3 -1 2 4
A を並べ替えて (-3,-1,2,4) とすると, 問題文中の条件における Y は (0,-3,-4,-2,2) となります. この Y に現れる任意の 1 未満の値は, Y に現れる任意の 1 以上の値より前に現れています.
入力例 2
4 -1 1 -2 3 -4
出力例 2
No
入力例 3
10 1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 3
Yes -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Score : 300 points
Problem Statement
You are given integers N and K.
The cumulative sums of an integer sequence X=(X_1,X_2,\dots ,X_N) of length N is defined as a sequence Y=(Y_0,Y_1,\dots ,Y_N) of length N+1 as follows:
- Y_0=0
- Y_i=\displaystyle\sum_{j=1}^{i}X_j\ (i=1,2,\dots ,N)
An integer sequence X=(X_1,X_2,\dots ,X_N) of length N is called a good sequence if and only if it satisfies the following condition:
- Any value in the cumulative sums of X that is less than K appears before any value that is not less than K.
- Formally, for the cumulative sums Y of X, for any pair of integers (i,j) such that 0 \le i,j \le N, if (Y_i < K and Y_j \ge K), then i < j.
You are given an integer sequence A=(A_1,A_2,\dots ,A_N) of length N. Determine whether the elements of A can be rearranged to a good sequence. If so, print one such rearrangement.
Constraints
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq K \leq 10^9
- -10^9 \leq A_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \cdots A_N
Output
If the elements of A can be rearranged to a good sequence, print the rearranged sequence (A^{\prime}_1,A^{\prime}_2,\dots ,A^{\prime}_N) in the following format:
Yes
A^{\prime}_1 A^{\prime}_2 \cdots A^{\prime}_N
If there are multiple valid rearrangements, any of them is considered correct.
If a good sequence cannot be obtained, print No.
Sample Input 1
4 1 -1 2 -3 4
Sample Output 1
Yes -3 -1 2 4
If you rearrange A to (-3,-1,2,4), the cumulative sums Y in question will be (0,-3,-4,-2,2). In this Y, any value less than 1 appears before any value not less than 1.
Sample Input 2
4 -1 1 -2 3 -4
Sample Output 2
No
Sample Input 3
10 1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 3
Yes -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000 1000000000 1000000000