201280: [AtCoder]ARC128 A - Gold and Silver

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $400$ points

Problem Statement

Snuke has $1$ gram of gold and $0$ grams of silver now. He will do trading of gold and silver for the following $N$ days. On each day, he has two choices: do nothing, or make a trade. If he trades on Day $i$ ($1 \leq i \leq N$), the following will happen.

  • If he has $x$ grams of gold before the trade, exchange all of it for $x \times A_i$ grams of silver. On the other hand, if he has $x$ grams of silver, exchange all of it for $x / A_i$ grams of gold.

Snuke's objective is to maximize the amount of gold he has in the end. Find one way to achieve his objective.

Constraints

  • $2 \leq N \leq 200000$
  • $1 \leq A_i \leq 10^9$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

Output

Print the answer in the following format:

$v_1$ $v_2$ $\cdots$ $v_N$

Here, $v_i$ is an integer representing the action on Day $i$ ($0 \leq v_i \leq 1$). $v_i=0$ means he does nothing, and $v_i=1$ means he makes a trade. If there are multiple possible solutions, printing any of them will be considered correct.


Sample Input 1

3
3 5 2

Sample Output 1

0 1 1

The optimal sequence of actions is as follows.

  • Day $1$: Do nothing.

  • Day $2$: Exchange $1$ gram of gold for $5$ grams of silver.

  • Day $3$: Exchange $5$ grams of silver for $2.5$ grams of gold.


Sample Input 2

4
1 1 1 1

Sample Output 2

0 0 0 0

$(v_1,v_2,v_3,v_4)=(1,1,1,1)$, for example, is also considered correct.


Sample Input 3

10
426877385 186049196 624834740 836880476 19698398 709113743 436942115 436942115 436942115 503843678

Sample Output 3

1 1 0 1 1 1 1 0 0 0

Input

题意翻译

你最近在做金银交易,在接下来的 $N$ 天中,每天都有一个汇率 $A_i$。起初你有 $1$克金,没有银。 每天你可以兑换手中的金银(也可以不兑换),如果你手中有 $x$ 克金,可以**全部**兑换为 $x \times A_i$ 克银,同理,如果有 $x$ 克银,可以全部兑换为 $x / A_i$ 克金。 请问 $N$ 天后最多能得到多少克金。你只需要**输出方案**。

加入题单

上一题 下一题 算法标签: