COCI '15 Contest 5 #4 Poplava

View as PDF

Submit solution

Points: 12
Time limit: 1.0s
Memory limit: 64M

Problem type

Mirko dreamt of a histogram last night that consists of N columns. Each column is one meter wide and the heights of the columns in meters are h_1, h_2, \dots, h_N.

The capacity of a histogram is the maximal amount of water that a histogram can hold so that the configuration of the water is "stable", or, in other words, that it doesn't move under the influence of gravity. The image on the right depicts an example of a stable configuration.

Formally, let us denote the heights of water above the columns with v_1, v_2, \dots, v_N.

The configuration of the water is stable if the following holds:

  • h_i + v_i \le h_{i-1} + v_{i-1}, for each i \ge 2 such that v_i > 0
  • h_i + v_i \le h_{i+1} + v_{i+1}, for each i \le N-1 such that v_i > 0
  • v_1 = 0 and v_N = 0

When Mirko woke up, he wanted to know whether he could somehow choose the heights of columns that are a permutation of the set \{1, 2, \dots, N\} such that the capacity of such histogram is equal to its lucky number X. Help Mirko and find one histogram that meets his requirements.


The first line of input contains integers N and X (1 \le N \le 1\,000\,000, 1 \le X \le 10^{15}).


If a histogram of capacity exactly X does not exist, output -1. Otherwise, output numbers h_1, h_2, \dots, h_N that meet the given requirements in the first line separated by space. If there are multiple such solutions, output any.

Sample Input 1

3 1

Sample Output 1

3 1 2

Explanation for Sample Output 1

In this configuration, it holds v_i = 0, v_2 = 1, v_3 = 0.

Sample Input 2

4 1

Sample Output 2

4 3 1 2

Explanation for Sample Output 2

In this configuration it holds v_i = 0, v_2 = 0, v_3 = 1, v_4 = 0.

Sample Input 3

8 17

Sample Output 3

6 2 3 1 8 4 5 7

Explanation for Sample Output 3

The sample corresponds to the image from the task.


There are no comments at the moment.