Poplava
레이팅 미적용의견: 0
\(5^{th}\) round, January \(16^{th}\) 2016
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, h2, ..., 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 un-
der the influence of gravity. The image on the
right depicts an example of a stable configura-
tion.
Formally, let us denote the heights of water above
the columns with \(v_{1}\), v_{2}, ..., v_{N}.
The configuration of the water is stable if the fol-
lowing holds:
• \(h@@RISE_MATH_BLOCK_0@@i\) ⩽\(h@@RISE_MATH_BLOCK_1@@i - 1\), for each \(i\) ⩾2 such
that \(v_{i} > 0\)
• \(h@@RISE_MATH_BLOCK_2@@i\) ⩽\(h@@RISE_MATH_BLOCK_3@@i+1\), for each \(i\) ⩽\(N - 1\)
such that \(v@@RISE_MATH_BLOCK_4@@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, ..., 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 ⩽\(N\) ⩽1 000 000, 1 ⩽\(X\) ⩽\(10^{15}\)).
If a histogram of capacity exactly \(X\) does not exist, outp\(ut - 1\). Otherwise, output numbers \(h\)1, h2, ..., h_{N}
that meet the given requirements in the first line separated by space. If there are multiple such solu-
tions, output any.
3 1
4 1
8 17output
output
3 1 2
4 3 1 2
6 2 3 1 8 4 5 7Clarification of the first example: In this configuration, it holds v1 = 0, v2 = 1, v3 = 0.
Clarification of the second example: In this configuration, it holds v1 = 0, v2 = 0, v3 = 1, v4 = 0.
Clarification of the third example: The sample corresponds to the image from the task.
평가 및 의견
Poplava
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Poplava