Doremy's IQ (Codeforces 1707A)
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 sys
input = sys.stdin.readline
for _ in range(int(input())):
    (n, q) = list(map(int, input().split()))
    a = list(map(int, input().split()))
    b = ['0'] * n
    rest_q = 0
    for i in range(n - 1, -1, -1):
        if rest_q >= a[i]:
            b[i] = '1'
        elif rest_q < q and a[i] > rest_q:
            rest_q += 1
            b[i] = '1'
        else:
            pass
    print(''.join(b))

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

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
from os import path
alpha = 'abcdefghijklmnopqrstuvwxyz'
from sys import maxsize
from itertools import permutations
import math

def arr_input():
    return list(map(int, input().split()))

def mul_input():
    return map(int, input().split())

def int_inp():
    return int(input())
from math import gcd
from collections import Counter
from functools import reduce

def is_prime(n):
    """"""
    if n == 1:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

def DFSUtil(v, visited, m):
    visited.add(v)
    print(v, end=' ')
    for neighbour in m[v]:
        if neighbour not in visited:
            DFSUtil(neighbour, visited, m)

def DFS(v, m):
    visited = set()
    DFSUtil(v, visited, m)
from collections import defaultdict

def solution():
    (n, q) = map(int, input().split())
    a = list(map(int, input().split()))
    b = [0] * n
    q_val = 0
    for i in range(n - 1, -1, -1):
        if a[i] <= q_val:
            b[i] = 1
        elif q_val < q:
            q_val += 1
            b[i] = 1
    print(''.join(map(str, b)))

def main():
    if path.exists('input.txt'):
        sys.stdin = open('input.txt', 'r')
        sys.stdout = open('output.txt', 'w')
    testcases = int(input())
    for _ in range(testcases):
        solution()

def main1():
    testcases = 1
    for _ in range(testcases):
        solution()
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
    return sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()