Doremy's IQ

题意翻译

## 题目描述 哆来咪·苏伊特参加了 $n$ 场比赛。 比赛 $i$ 只能在第 $i$ 天进行。比赛 $i$ 的难度为 $a_i$。最初，哆来咪的 IQ 为 $q$ 。 在第 $i$ 天，哆来咪将选择是否参加比赛 i。只有当她当前的 IQ 大于 $0$ 时，她才能参加比赛。 如果哆来咪选择在第 $i$ 天参加比赛 $i$，则会发生以下情况： - 如果 $a_i>q$，哆来咪会觉得自己不够聪明，所以 $q$ 将会减 $1$； - 否则，什么都不会改变。 如果她选择不参加比赛，一切都不会改变。哆来咪想参加尽可能多的比赛。请给哆来咪一个解决方案。 ## 输入格式 第一行包含一个正整数 $t$ ($1\le t\le10^4$) ，表示测试数据的组数。 第二行包含两个整数 $n$ 和 $q$ ($1\le n\le10^5$, $1\le q\le10^9$)，表示比赛次数和哆来咪最开始时的 IQ。 第三行包含 $n$ 个整数 $a_1,a_2⋯a_n$($1\le a_i≤10^9$)，表示每场比赛的难度。 数据保证 $n$ 之和不超过 $10^5$。 ## 输出格式 对于每组数据，输出一个二进制字符串 $s$，如果哆来咪应该选择参加比赛 $i$，则 $s_i=1$，否则 $s_i=0$。 字符串中 $1$ 的数量应该尽可能的多，并且当她的 IQ 为 $0$ 或更低时，她不应该参加比赛。 如果有多个解决方案，你可以输出任意一个。 ## 样例说明 在第一个测试用例中，哆来咪参加了唯一的比赛。她的 IQ 没有下降。 在第二个测试用例中，哆来咪参加了两个比赛。在参加比赛 $2$ 后，她的 IQ 下降了 $1$。 在第三个测试用例中，哆来咪参加了比赛 $1$ 和比赛 $2$。她的 IQ 在参加比赛 $2$ 后降至 $0$，因此她无法参加比赛 $3$。

题目描述

Doremy is asked to test $ n $ contests. Contest $ i $ can only be tested on day $ i $ . The difficulty of contest $ i $ is $ a_i $ . Initially, Doremy's IQ is $ q $ . On day $ i $ Doremy will choose whether to test contest $ i $ or not. She can only test a contest if her current IQ is strictly greater than $ 0 $ . If Doremy chooses to test contest $ i $ on day $ i $ , the following happens: - if $ a_i>q $ , Doremy will feel she is not wise enough, so $ q $ decreases by $ 1 $ ; - otherwise, nothing changes. If she chooses not to test a contest, nothing changes.Doremy wants to test as many contests as possible. Please give Doremy a solution.

输入输出格式

输入格式

The input consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1\le t\le 10^4 $ ) — the number of test cases. The description of the test cases follows. The first line contains two integers $ n $ and $ q $ ( $ 1 \le n \le 10^5 $ , $ 1 \le q \le 10^9 $ ) — the number of contests and Doremy's IQ in the beginning. The second line contains $ n $ integers $ a_1,a_2,\cdots,a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the difficulty of each contest. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case, you need to output a binary string $ s $ , where $ s_i=1 $ if Doremy should choose to test contest $ i $ , and $ s_i=0 $ otherwise. The number of ones in the string should be maximum possible, and she should never test a contest when her IQ is zero or less. If there are multiple solutions, you may output any.

输入输出样例

输入样例 #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

说明

In the first test case, Doremy tests the only contest. Her IQ doesn't decrease. In the second test case, Doremy tests both contests. Her IQ decreases by $ 1 $ after testing contest $ 2 $ . In the third test case, Doremy tests contest $ 1 $ and $ 2 $ . Her IQ decreases to $ 0 $ after testing contest $ 2 $ , so she can't test contest $ 3 $ .

**题目大意：**
哆来咪参加了n场比赛，每场比赛有难度值，初始时她的IQ值为q。每天，她可以选择参加比赛或跳过。如果参赛，且比赛难度大于她的IQ，则IQ减1；否则，IQ不变。如果跳过，则IQ不变。当IQ为0时，她不能参赛。求哆来咪最多能参加多少场比赛的方案。

**输入格式：**
第一行包含一个整数t，表示测试数据的组数。
每组数据包含两行，第一行为两个整数n和q，表示比赛次数和初始IQ值。
第二行为n个整数，表示每场比赛的难度。

**输出格式：**
对于每组数据，输出一个二进制字符串s，如果哆来咪应该选择参加比赛i，则si=1，否则si=0。字符串中1的数量应尽可能多，并且当她的IQ为0或更低时，她不应该参加比赛。

**样例说明：**
在第一个测试用例中，哆来咪参加了唯一的比赛，IQ没有下降。
在第二个测试用例中，哆来咪参加了两个比赛，参加第二个比赛后，IQ下降了1。
在第三个测试用例中，哆来咪参加了第一和第二场比赛，参加第二场比赛后，IQ降至0，因此她无法参加第三场比赛。**题目大意：** 哆来咪参加了n场比赛，每场比赛有难度值，初始时她的IQ值为q。每天，她可以选择参加比赛或跳过。如果参赛，且比赛难度大于她的IQ，则IQ减1；否则，IQ不变。如果跳过，则IQ不变。当IQ为0时，她不能参赛。求哆来咪最多能参加多少场比赛的方案。 **输入格式：** 第一行包含一个整数t，表示测试数据的组数。 每组数据包含两行，第一行为两个整数n和q，表示比赛次数和初始IQ值。 第二行为n个整数，表示每场比赛的难度。 **输出格式：** 对于每组数据，输出一个二进制字符串s，如果哆来咪应该选择参加比赛i，则si=1，否则si=0。字符串中1的数量应尽可能多，并且当她的IQ为0或更低时，她不应该参加比赛。 **样例说明：** 在第一个测试用例中，哆来咪参加了唯一的比赛，IQ没有下降。 在第二个测试用例中，哆来咪参加了两个比赛，参加第二个比赛后，IQ下降了1。 在第三个测试用例中，哆来咪参加了第一和第二场比赛，参加第二场比赛后，IQ降至0，因此她无法参加第三场比赛。