最高分数:1500 点
问题陈述
E869120 编码员决定每年给 square1001 一个序列作为生日礼物,供下一年使用 Q 年。
由于square1001说“序列的长度越短越好”,所以序列的长度应该尽可能短。
而且,还有自古流传下来的“AtCoder的感知”,所以他也决定根据这个感知来确定顺序。
《AtCoder感知》内容如下:
- 按顺序排列的元素应该是 不同.
- 即将给出的序列应该恰好具有 K 增加子序列。 (K 是“圣号”)
- 的子序列 A = (A_1, A_2, ..., A_N) 是可以通过删除一些(可能是零个或全部)元素而不改变剩余元素的顺序来生成的序列。
- 注意:空序列也作为递增子序列包含在内。另外,即使删除的地方不同,当得到的子序列相同时,也视为同一个子序列。
- 例如,如果 A = (3, 4, 1, 2),有 7 增加子序列: (), (1), (2), (3), (4), (1, 2), (3, 4).
在AtCoder中,“圣数”每年都会发生变化。在 i- 第一年,圣数是 K_i.
请找到E869120编码员每年应该赠送的序列。
输入
输入由标准输入按以下格式给出:
Q K_1 K_2 K_3 ... K_Q
输出
打印 Q 行如下:
(Information of sequence in 1-st year) (Information of sequence in 2-nd year) (Information of sequence in 3-rd year) ... (Information of sequence in Q-th year)
您应该输出序列信息如下:
N A_1 A_2 A_3 ... A_N
注意 N 是长度 A.
序列应满足以下条件:
- 0 \leq N \leq 128
- 0 \leq A_i \leq 999
- A_i \neq A_j (i \neq j)
约束
- Q 是介于 1 和 1 \ 000 (含)
- K_i 是介于 1 和 5 \ 000 \ 000 \ 000 \ 000 \ 000 \ 000 \ (= 5 \times 10^{18}) (含)
子任务/评分
- (30分):K_i \leq 100
- (70分):K_i \leq 1 \ 500
- (1400分):没有额外的限制。
在子任务中 3,分数将确定如下。
让 L 是最大值 N 在此测试用例中,让 L' 是最大值 L 在子任务中的所有测试用例中 3.
- 120 \leq L' \leq 128 : 125 子任务中的点 3
- 100 \leq L' \leq 119 : 1400 \times 5^{-(L' - 99) / 20} 子任务中的点 3
- 0 \leq L' \leq 99 : 1400 子任务中的点 3
示例输入 1
2 5 10
示例输出 1
3 2 3 1 6 8 6 9 1 2 0
E869120给出的序列 1今年是 (2, 3, 1).
有 5 增加子序列: (), (1), (2), (3), (2, 3).
示例输入 2
3 20 100 869120
示例输出 2
9 9 7 3 6 5 8 4 1 2 10 0 5 9 3 6 1 4 2 7 8 72 47 45 28 9 41 50 33 61 27 15 38 54 52 22 57 7 30 12 46 21 19 8 71 20 23 6 18 26 17 39 4 53 44 3 31 68 29 42 62 37 69 67 40 65 2 55 36 35 11 49 24 25 43 48 0 1 16 10 70 66 64 32 5 51 60 63 58 56 59 13 14 34