分数: 400 点
问题陈述
Snuke 有 1 克金和 0 现在克银。 他将进行以下黄金和白银的交易 N 天。 每天,他都有两个选择:什么也不做,或者进行交易。 如果他在当天交易 i (1 \leq i \leq N),将会发生以下情况。
- 如果他有 x 交易前黄金克数,全部兑换 x \times A_i 银克数。 另一方面,如果他有 x 克银子,全部兑换 x / A_i 克金。
Snuke 的目标是最大化他最终拥有的黄金数量。 找到一种方法来实现他的目标。
约束
- 2 \leq N \leq 200000
- 1 \leq A_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \cdots A_N
输出
按以下格式打印答案:
v_1 v_2 \cdots v_N
在这里, v_i 是一个整数,表示当天的操作 i (0 \leq v_i \leq 1). v_i=0 表示他什么也没做,并且 v_i=1 表示他进行了交易。 如果有多种可能的解决方案,则打印其中任何一个都将被认为是正确的。
示例输入 1
3 3 5 2
示例输出 1
0 1 1
最佳操作顺序如下。
-
天 1:什么都不做。
-
天 2:交换 1 克金为 5 银克数。
-
天 3:交换 5 克银为 例如, 2.5 克金。
示例输入 2
4 1 1 1 1
示例输出 2
0 0 0 0
(v_1,v_2,v_3,v_4)=(1,1,1,1)也被认为是正确的。
示例输入 3
10 426877385 186049196 624834740 836880476 19698398 709113743 436942115 436942115 436942115 503843678
示例输出 3
1 1 0 1 1 1 1 0 0 0