Average Query

steinum testing contest
Limits 2s, 512 MB

You are given an array s1,s2,,sns_1, s_2, \ldots, s_n of length nn and an arbitrary integer xx.

For an array, c1,c2,,cnc_1, c_2,\ldots, c_n of length nn, we can define its score as 1L×i=1nci×si\frac{1}{L}\times \sum_{i=1}^{n}{c_i\times s_i} and cost as U2LU-2^{-L}.

where U=i=1n[ci>0]U = \sum_{i=1}^{n}{[c_i > 0]} and L=i=1nciL = \sum_{i=1}^{n}{c_i}.

Now, we have to print an array a1,a2,,ana_1, a_2,\ldots, a_n of length nn whose score is equal to xx. If there are multiple such arrays print the array whose cost is minimum. If there are multiple such arrays with minimum cost print any.

  • [E][E] refers to the boolean expression, i.e. [E]=1[E] = 1 when EE is true, and 00 otherwise.


The first line of the input contains integers n(1n105)n(1\le n \le 10^5) and x(1x109)x(1\le x \le 10^9)— the size of the set ss and an arbitrary integer mentioned in the statement.

The second line contains nn integers s1,s2,s3,,sns_1, s_2, s_3,\ldots, s_n(1si109)(1\le s_i \le 10^{9}), all sis_i are distinct — the elements of the array ss.


If there is no array whose score is equal to xx, print NO in a single line.

If there is a solution, print YES and in the second line print nn space separated integers a1,a2,,an(0ai109)a_1, a_2,\ldots, a_n(0\le a_i \le 10^9) — the array aa satisfying the conditions mentioned in the statement.


3 2
1 3 5
1 1 0


Login to submit.


80% Solution Ratio
AlfehsaniEarliest, 1M ago
ash_98Fastest, 0.0s
ash_98Lightest, 37 kB
mdshadeshShortest, 3111B
Toph uses cookies. By continuing you agree to our Cookie Policy.