Doremy's IQ (Codeforces 1708C)
Tags: Greedy, binary search

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.

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

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

Sample Inputs:
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

Sample Outputs:
1
11
110
1110
01111

Solution (Python):
import math
import itertools
import heapq
from math import floor, ceil
from collections import deque
import sys
from collections import Counter
I = lambda : list(map(int, input().split()))
MAP = lambda : map(int, input().split())
input = sys.stdin.readline
sys.setrecursionlimit(10000)
MOD = 10 ** 9 + 7

def lcm(a, b):
    return abs(a * b) // math.gcd(a, b)

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def isSubsequence(s, t):
    for i in range(0, len(s)):
        try:
            index = t.index(s[i])
        except ValueError:
            return False
        t = t[index + 1:]
    return True

def bisect_right(a, x):
    (lo, hi) = (0, len(a))
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] > x:
            hi = mid
        else:
            lo = mid + 1
    return lo

def bisect_left(a, x):
    (lo, hi) = (0, len(a))
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

def binary_search(nums, target):
    (left, right) = (0, len(nums) - 1)
    while left <= right:
        pivot = left + (right - left) // 2
        if nums[pivot] == target:
            return pivot
        if target < nums[pivot]:
            right = pivot - 1
        else:
            left = pivot + 1
    return -1

def prefixSum(arr):
    dp = [arr[0]]
    arrLen = len(arr)
    for i in range(1, arrLen):
        dp.append(dp[-1] + arr[i])
    return dp

def suffixSum(arr):
    arrLen = len(arr)
    dp = [0] * arrLen
    dp[-1] = arr[-1]
    for i in range(N - 2, -1, -1):
        dp[i] = dp[i + 1] + arr[i]
    return dp

def fun():
    return

def solve():
    (N, iq) = map(int, input().split())
    arr = I()
    ans = [0] * N
    chIQ = 0
    for i in range(N - 1, -1, -1):
        if arr[i] <= chIQ:
            ans[i] = 1
        elif iq > chIQ:
            chIQ += 1
            ans[i] = 1
        else:
            pass
    print(''.join([str(i) for i in ans]))
TC = 1
TC = int(input())
for testcases in range(TC):
    solve()

Solution (Python):
t = int(input())
for _ in range(t):
    (n, q) = map(int, input().split())
    a = list(map(int, input().split()))
    a.reverse()
    b = ''
    Q = 0
    for r in a:
        if r <= Q:
            b += '1'
        elif Q < q:
            Q += 1
            b += '1'
        else:
            b += '0'
    print(b[::-1])

Solution (Python):
for _ in range(int(input())):
    (n, q) = map(int, input().split())
    ls = list(map(int, input().split()))
    ans = ['0'] * n
    iq = 0
    for i in range(n - 1, -1, -1):
        if ls[i] <= iq:
            ans[i] = '1'
        elif iq < q:
            iq += 1
            ans[i] = '1'
    print(''.join(ans))