Codeforces Global Round 12 |
---|
Закончено |
На платформе CodeCook для соревнований по спортивному программированию у каждого человека есть график его рейтинга, описываемый массивом целых чисел $$$a$$$ длины $$$n$$$. Вы обновляете инфраструктуру, поэтому вы создали программу, сжимающую эти графики.
Программа работает следующим образом. Задается целое число $$$k$$$. Программа берет минимум на каждом последовательном подмассиве длины $$$k$$$ в массиве $$$a$$$.
Более формально, для массива $$$a$$$ длины $$$n$$$ и целого числа $$$k$$$, определим $$$k$$$-сжатие массива $$$a$$$ как массив $$$b$$$ длины $$$n-k+1$$$, такой что $$$$$$b_j =\min_{j\le i\le j+k-1}a_i$$$$$$
Например, $$$3$$$-сжатие массива $$$[1, 3, 4, 5, 2]$$$ это $$$[\min\{1, 3, 4\}, \min\{3, 4, 5\}, \min\{4, 5, 2\}]=[1, 3, 2].$$$
Перестановка длины $$$m$$$ это массив, состоящий из $$$m$$$ различных целых чисел от $$$1$$$ до $$$m$$$ в некотором порядке. Например, $$$[2,3,1,5,4]$$$ это перестановка, но $$$[1,2,2]$$$ это не перестановка ($$$2$$$ встречается дважды в массиве) и $$$[1,3,4]$$$ это тоже не перестановка ($$$m=3$$$, но в массиве есть число $$$4$$$).
$$$k$$$-сжатие массива рейтинга сделает пользователей CodeCook счастливыми, если оно будет перестановкой. Вам дан массив $$$a$$$, определите для всех $$$1\leq k\leq n$$$ будут ли счастливы пользователи CodeCook после $$$k$$$-сжатия этого массива или нет.
В первой строке находится единственное целое число $$$t$$$ ($$$1\leq t\leq 10^4$$$) — количество наборов входных данных.
В первой строке описания каждого набора входных данных находится единственное целое число $$$n$$$ ($$$1\leq n\leq 3\cdot 10^5$$$) — длина массива.
Во второй строке описания каждого набора входных данных находится $$$n$$$ целых чисел $$$a_1,\ldots,a_n$$$ ($$$1\leq a_i\leq n$$$) — элементы массива.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3\cdot 10^5$$$.
Для каждого набора входных данных выведите бинарную строку длины $$$n$$$.
$$$k$$$-й символ строки должен быть $$$1$$$, если пользователи CodeCook будут счастливы после $$$k$$$-сжатия массива $$$a$$$ и $$$0$$$, иначе.
5 5 1 5 3 4 2 4 1 3 2 1 5 1 3 3 3 2 10 1 2 3 4 5 6 7 8 9 10 3 3 3 2
10111 0001 00111 1111111111 000
В первом наборе входных данных $$$a=[1, 5, 3, 4, 2]$$$.
Название |
---|