Codeforces Round 808 (Div. 1) |
---|
Закончено |
Дореми попросили протестировать $$$n$$$ контестов. Контест $$$i$$$ может быть протестирован только в день $$$i$$$. Сложность контеста $$$i$$$ равна $$$a_i$$$. В начале показатель IQ Дореми равен $$$q$$$. В день $$$i$$$ Дореми решает, протестирует ли она контест $$$i$$$ или нет. Она может протестировать контест только в случае, если её текущий показатель IQ строго больше $$$0$$$.
Если Дореми решает протестировать контест $$$i$$$ в день $$$i$$$, то происходит следующее:
Дореми хочет протестировать как можно больше контестов. Помогите Дореми найти оптимальное решение.
Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных в тесте. Далее следует описание наборов.
Первая строка каждого набора содержит целые числа $$$n$$$ и $$$q$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le q \le 10^9$$$) — число контестов и показатель IQ Дореми в начале.
Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1,a_2,\cdots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — сложность каждого контеста.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора выведите бинарную строку $$$s$$$, где $$$s_i=1$$$ если Дореми должна протестировать контест $$$i$$$, и $$$s_i=0$$$ иначе. Число единиц в строке должно быть максимально возможным, и при этом она не должна тестировать контест, когда её показатель IQ меньше либо равен нулю.
Если существуют несколько решений, выведите любое из них.
51 112 11 23 11 2 14 21 4 3 15 25 1 2 4 3
1 11 110 1110 01111
В первом наборе входных данных Дореми тестирует единственный имеющийся контест. Её показатель IQ не уменьшается.
Во втором наборе входных данных Дореми тестирует оба имеющихся контеста. Её показатель IQ уменьшается на $$$1$$$ после тестирования контеста $$$2$$$.
В третьем наборе входных данных Дореми тестирует контесты $$$1$$$ и $$$2$$$. Её показатель IQ уменьшается до $$$0$$$ после тестирования контеста $$$2$$$, поэтому она не может протестировать контест $$$3$$$.
Название |
---|