33OJ
登录 注册

#P17716. [HexOI Round 1] 变魔术 / magic

[HexOI Round 1] 变魔术 / magic

背景

题目来源:【HT-130-Div.3】核桃 CSP-J 组模拟赛

HexOI 欢迎您。

题目描述

小 Hex 有 nn 块积木!每块积木都有一个「美丽度」,第 ii 块积木的美丽度为 aia_i。

现在小 Hex 想向小 Toast 表演魔术。他希望用一种特殊的魔术技巧来整理他的积木,最后只留下小 Toast 最喜欢的积木。

具体地,他整理积木的方法如下:

  1. 小 Hex 有一个淘汰盒。初始时,他手上有所有的积木,并且淘汰盒是空的。
  2. 小 Hex 会把他目前手上所有的积木分为若干堆,并计算每堆所有积木的美丽度之和;
  3. 小 Hex 会选择美丽度之和最高的一堆积木(如果有并列则任取一堆),保留这一堆积木,并把其他所有的积木放到淘汰盒中;
  4. 如果操作结束后小 Hex 只剩恰好一个积木,那么他会把这个积木展示给小 Toast;否则,回到「第 2 步」继续。

然而,小 Hex 并不知道小 Toast 最喜欢的积木,因此他要对所有的情况做好准备。现在他想知道,对于所有的 i=1,2,⋯ ,ni=1,2,\cdots,n,假设小 Toast 喜欢第 ii 块积木,他能否恰好选择出小 Toast 喜欢的那个积木?

输入格式

第一行一个正整数 nn。

第二行 nn 个正整数 a1,a2,…,ana_1,a_2,\dots,a_n。

输出格式

一行 nn 个整数,第 ii 个数表示假设小 Toast 喜欢第 ii 块积木时,小 Hex 能否恰好选出他喜欢的积木。为 11 表示可以,为 00 表示不行。

3
1 2 3

0 1 1

6
1 10 5 3 7 9

0 1 1 0 1 1

提示

【样例 1 解释】

小 Hex 可以用下面的方法来选出第二块积木:

  • 把所有积木按编号分为 {1,2}\{1,2\} 和 {3}\{3\} 两堆积木,此时两堆积木的美丽度之和分别为 3,33,3。保留第一堆积木,将 33 号积木放进淘汰盒。
  • 把 1,21,2 号积木按编号分为 {1}\{1\} 和 {2}\{2\} 两堆积木,此时两堆积木的美丽度之和分别为 1,21,2。保留第二堆积木,将 11 号积木放进淘汰盒。
  • 此时,小 Hex 只剩下 22 号积木。

小 Hex 可以用下面的方法来选出第三块积木:

  • 把所有积木按编号分为 {1}\{1\},{2}\{2\} 和 {3}\{3\} 三堆积木,此时三堆积木的美丽度之和分别为 1,2,31,2,3。保留第三堆积木,将 1,21,2 号积木放进淘汰盒。
  • 此时,小 Hex 只剩下 33 号积木。

可以证明,无论小 Hex 怎样操作,他都无法选出第一块积木。

【样例 3】

见选手目录下的 magic/magic3.in 与 magic/magic3.ans。

该样例满足测试点 4,54,5 的约束条件。

【样例 4】

见选手目录下的 magic/magic4.in 与 magic/magic4.ans。

该样例满足测试点 7∼97\sim 9 的约束条件。

【样例 5】

见选手目录下的 magic/magic5.in 与 magic/magic5.ans。

该样例满足测试点 10∼1210\sim 12 的约束条件。

【样例 6】

见选手目录下的 magic/magic6.in 与 magic/magic6.ans。

该样例满足测试点 13∼2013\sim 20 的约束条件。

【数据范围】

对于所有测试数据,保证:

  • 1≤n≤1051\leq n\leq 10^5。
  • 对于所有 1≤i≤n1\leq i\leq n,均有 1≤ai≤1091\leq a_i\leq 10^9。

::cute-table{tuack}

测试点编号 nn ai(1≤i≤n)a_i(1\leq i\leq n) 特殊性质
11 ≤3\leq 3 ≤109\leq 10^9 无
2,32,3 ≤10\leq 10 ^ ^
4,54,5 ≤5×103\leq 5\times 10^3 ≤2\leq 2
66 ^ ≤109\leq 10^9 A
7∼97\sim 9 ^ B
10∼1210\sim 12 无
13∼2013\sim 20 ≤105\leq 10^5

特殊性质 A:保证 a1=a2=⋯=ana_1=a_2=\cdots=a_n。

特殊性质 B:对于所有 i(1≤i≤n)i(1\leq i\leq n),都有 ai=109a_i=10^9 或 ai=109−1a_i=10^9-1。