Codeforces Round 658 (Div. 1) |
---|
Закончено |
Пусть $$$a$$$ и $$$b$$$ это два массива, имеющих длины $$$n$$$ и $$$m$$$, соответственно, такие что ни один элемент первого массива не равен ни одному элементу второго массива. Мы можем определить новый массив $$$\mathrm{merge}(a,b)$$$ длины $$$n+m$$$ по следующему рекурсивному правилу:
Этот алгоритм имеет замечательное свойство: если $$$a$$$ и $$$b$$$ были отсортированы, тогда $$$\mathrm{merge}(a,b)$$$ тоже будет отсортированным. Например, этот алгоритм используется для сортировки слиянием. Для этой задачи, тем не менее, мы рассматриваем этот алгоритм для неотсортированных массивов тоже. Например, если $$$a=[3,1]$$$ и $$$b=[2,4]$$$, тогда $$$\mathrm{merge}(a,b)=[2,3,1,4]$$$.
Перестановкой называется массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в некотором порядке. Например, $$$[2,3,1,5,4]$$$ это перестановка, но $$$[1,2,2]$$$ это не перестановка ($$$2$$$ встречается дважды в массиве) и $$$[1,3,4]$$$ это тоже не перестановка ($$$n=3$$$, но число $$$4$$$ встречается в массиве).
У вас есть перестановка $$$p$$$ длины $$$2n$$$. Определите, существуют ли два массива $$$a$$$ и $$$b$$$, каждый из которых имеет длину $$$n$$$, оба массива не имеют общих элементов и выполнено, что $$$p=\mathrm{merge}(a,b)$$$.
В первой строке находится единственное целое число $$$t$$$ ($$$1\le t\le 1000$$$) — количество наборов входных данных. Следующие $$$2t$$$ строк содержат описания наборов входных данных.
В первой строке каждого набора входных данных находится единственное целое число $$$n$$$ ($$$1\le n\le 2000$$$).
Во второй строке каждого набора входных данных находится $$$2n$$$ целых чисел $$$p_1,\ldots,p_{2n}$$$ ($$$1\le p_i\le 2n$$$). Гарантируется, что $$$p$$$ является перестановкой.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2000$$$.
Для каждого набора входных данных выведите «YES», если существуют массивы $$$a$$$, $$$b$$$, каждый длины $$$n$$$, которые не имеют общих элементов, такие что $$$p=\mathrm{merge}(a,b)$$$. Иначе выведите «NO».
6 2 2 3 1 4 2 3 1 2 4 4 3 2 6 1 5 7 8 4 3 1 2 3 4 5 6 4 6 1 3 7 4 5 8 2 6 4 3 2 5 1 11 9 12 8 6 10 7
YES NO YES YES NO NO
В первом наборе входных данных $$$[2,3,1,4]=\mathrm{merge}([3,1],[2,4])$$$.
Во втором наборе входных данных можно показать, что $$$[3,1,2,4]$$$ не является результатом функции merge для двух массивов длины $$$2$$$.
В третьем наборе входных данных $$$[3,2,6,1,5,7,8,4]=\mathrm{merge}([3,2,8,4],[6,1,5,7])$$$.
В четвертом наборе входных данных $$$[1,2,3,4,5,6]=\mathrm{merge}([1,3,6],[2,4,5])$$$.
Название |
---|