A4496 「ICPC World Finals 2025」叠杯子

暂无评定 传统题 ICPC 上传者
时间限制2000ms
内存限制2048MiB
通过 / 提交0/0

A4496「ICPC World Finals 2025」叠杯子

暂无评定 传统题 ICPC 上传者
时间限制2000ms
内存限制2048MiB
通过 / 提交0/0

题目描述

你有一堆 nn 个圆柱形的杯子,其中第 ii 个杯子的高度为 2i−12i-1 厘米。这些杯子的直径递增,当且仅当 i<ji<j 时,第 ii 个杯子可以套入第 jj 个杯子中。每个杯子的底部厚度为 11 厘米(这使得最小的杯子相当没用,因为它只有 11 厘米高,但你出于情感原因还是留着它)。

洗完所有杯子后,你将它们堆叠成一个塔。每个杯子都正向放置(即开口朝上),并且所有杯子的中心在垂直方向上对齐。塔的高度定义为从任何杯子的最低点到最高点的垂直距离。你想要知道应该按什么顺序放置杯子,才能使最终的高度(单位:厘米)是你最喜欢的数字。请注意,所有 nn 个杯子都必须使用。

例如,假设 n=4n=4 而你最喜欢的数字是 99。如果你按顺序放置高度为 7,3,5,17,3,5,1 的杯子,那么塔的总高度将为 99,如图 J.1 所示。

图 J.1:样例输出 1 的图示。

输入格式

输入仅包含一行,内含两个整数 nn 和 hh,其中 nn (1≤n≤2⋅105)(1 \leq n \leq 2 \cdot 10^{5}) 是杯子的数量,hh (1≤h≤4⋅1010)(1 \leq h \leq 4 \cdot 10^{10}) 是你最喜欢的数字。

输出格式

如果可以建造一个高度为 hh 的塔,则按顺序输出所有杯子的高度。否则,输出 impossible。如果存在多种满足条件的杯子排列顺序,你可以输出任何一种。

4 9

7 3 5 1

4 100

impossible