← 返回题目列表

Codeforces · 1707/A

A. 多蕾米的智商

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

Doremy 被要求测试 $$$n$$$ 比赛。比赛$$$i$$$只能在$$$i$$$当天进行测试。比赛$$$i$$$的难度为$$$a_i$$$。最初,Doremy 的智商是 $$$q$$$。在$$$i$$$当天,Doremy将选择是否参加$$$i$$$测试比赛。只有当她当前的 IQ 严格大于 $$$0$$$ 时,她才能参加比赛。

如果 Doremy 选择在 $$$i$$$ 天参加 $$$i$$$ 测试比赛,则会发生以下情况:

- 如果$$$a_i>q$$$,多蕾米会觉得自己不够聪明,所以$$$q$$$减少$$$1$$$;
- 否则,没有任何变化。

Doremy 希望测试尽可能多的比赛。请给多雷米一个解决方案。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le q \le 10^9$$$) — 比赛的次数和 Doremy 的智商。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\cdots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 每场比赛的难度。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例,您需要输出一个二进制字符串 $$$s$$$,其中 $$$s_i=1$$$ 如果 Doremy 应选择测试竞赛 $$$i$$$,否则 $$$s_i=0$$$。字符串中 1 的数量应尽可能多,并且当她的智商为零或更低时,她不应该参加比赛。

如果有多个解,则可以输出任意一个。

示例

输入 #1

5
1 1
1
2 1
1 2
3 1
1 2 1
4 2
1 4 3 1
5 2
5 1 2 4 3

输出 #1

1
11
110
1110
01111

注意

在第一个测试用例中,Doremy 测试了唯一的比赛。她的智商并没有下降。

在第二个测试用例中,Doremy 测试了两项比赛。在测试比赛 $$$2$$$ 后,她的智商下降了 $$$1$$$。

在第三个测试用例中,Doremy 测试竞赛 $$$1$$$ 和 $$$2$$$。在测试 $$$2$$$ 比赛后,她的智商下降到 $$$0$$$,因此她无法测试 $$$3$$$ 比赛。