← 返回题目列表

AtCoder · arc128_a

A. 金银

中文机器翻译题面 查看原题

分数: 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