Doremy's IQ
Contest: Codeforces Round 808 (Div. 1)
Difficulty rating: 1600
Tags: binary search, constructive algorithms, greedy, implementation

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.

Doremy wants to test as many contests as possible. Please give Doremy a solution.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
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

Example output:
1
11
110
1110
01111

Editorial:
Solution 1
We call contests that will decrease Doremy's IQ bad contests and the other good contests.
In the best solution(testing the maximum number of contests), there is always an index $$$x$$$.
• Contest $$$i$$$ ($$$i < x$$$) is tested, if Contest $$$i$$$ is good;
• Contest $$$i$$$ ($$$i \ge x$$$) is tested, no matter what kind of contest it is.
How to prove that this conclusion? For any choice, we can find the last contest $$$a$$$ that is not tested and the first bad contest $$$b$$$ that is tested. If $$$b<a$$$, we can give up contest $$$b$$$ and choose to test contest $$$a$$$, and the number of contests that is tested does not change. If $$$b>a$$$, there is already an valid $$$x$$$.
When $$$x$$$ is smallest, you can get the best solution. And we can find the smallest $$$x$$$ by binary search.
Time complexity $$$O(n \log n)$$$.
Solution 2
Consider everything in the reverse order.
Assume that Doremy has $$$Q=0$$$ IQ in the end. Consider whether a contest should be tested in the reverse order.
• $$$a_i\le Q$$$. Doremy should tested the contest because there is no decrease in her IQ.
• $$$a_i > Q$$$ and $$$Q < q$$$. If Doremy tests the contest, her IQ will decrease by $$$1$$$, so in the reverse order, her IQ increases by $$$1$$$; otherwise she just skipped the contest and nothing happened. Doremy can test at most $$$q$$$ contest with the $$$a_i>Q$$$ property. But if Doremy gets more IQ, she can participate more previous good contests. So she should test this contest.
• If $$$a_i > Q$$$ and $$$Q=q$$$, Doremy cannot test the contest because her IQ is not enough.
So you can determine whether every contest should be tested.
Time complexity $$$O(n)$$$.