Codeforces Round 934 (Div. 2) |
---|
Закончено |
Вам дан массив $$$a$$$ длины $$$2n$$$, в котором каждое целое число от $$$1$$$ до $$$n$$$ встречается ровно дважды.
Вам также дано целое число $$$k$$$ ($$$1 \leq k \leq \lfloor \frac{n}{2} \rfloor $$$).
Вам нужно найти два массива $$$l$$$ и $$$r$$$ длины $$$\mathbf{2k}$$$ каждый такие, что:
Можно доказать, что всегда существует хотя бы одна пара $$$l$$$ и $$$r$$$. Если существует несколько решений, вы можете вывести любое из них.
$$$^\dagger$$$ Последовательность $$$x$$$ является подмножеством последовательности $$$y$$$, если $$$x$$$ может быть получена из удалением нескольких (возможно, ни одного или всех) элементов $$$y$$$ и перестановкой оставшихся элементов. Например, $$$[3,1,2,1]$$$, $$$[1, 2, 3]$$$, $$$[1, 1]$$$ и $$$[3, 2]$$$ являются подмножествами $$$[1, 1, 2, 3]$$$ а $$$[4]$$$ и $$$[2, 2]$$$ не являются подмножествами $$$[1, 1, 2, 3]$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 5000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит $$$2$$$ целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 5 \cdot 10^4$$$, $$$1 \leq k \leq \lfloor \frac{n}{2} \rfloor $$$).
Вторая строка содержит $$$2n$$$ целых чисел $$$a_1, a_2, \ldots, a_{2n}$$$ ($$$1 \le a_i \le n$$$). Гарантируется, что каждое целое число от $$$1$$$ до $$$n$$$ встречается в $$$a$$$ ровно два раза.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^4$$$.
Для каждого набора входных данных выведите две строки.
В первой строке выведите $$$2k$$$ чисел $$$l_1, l_2, \ldots, l_{2k}$$$.
Во второй строке выведите $$$2k$$$ чисел $$$r_1, r_2, \ldots r_{2k}$$$.
Если существует несколько решений, вы можете вывести любое из них.
42 11 2 2 16 16 4 2 1 2 3 1 6 3 5 5 44 11 2 3 4 1 2 3 46 25 1 3 3 5 1 2 6 4 6 4 2
2 1 2 1 6 4 1 3 1 2 1 2 5 1 3 3 6 4 2 4
В первом наборе входных данных можно выбрать $$$l=[2,1]$$$ и $$$r=[2,1]$$$. $$$[2, 1]$$$ является подмножеством $$$[a_1, a_2]$$$, $$$[2, 1]$$$ является подмножеством $$$[a_3, a_4]$$$, и $$$2 \oplus 1 = 2 \oplus 1 = 3$$$.
Во втором наборе $$$6 \oplus 4 = 1 \oplus 3 = 2$$$.
Название |
---|