Codeforces Round 943 (Div. 3) |
---|
Закончено |
Бодя и Саша нашли перестановку $$$p_1,\dots,p_n$$$ и массив $$$a_1,\dots,a_n$$$. Они решили сыграть в известную игру в перестановке.
Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).
Каждый из них выбрал стартовую позицию в перестановке.
Игра длится $$$k$$$ ходов. Игроки делают ходы одновременно. На каждом ходу с каждым игроком происходит две вещи:
Зная стартовую позицию Боди $$$P_B$$$ и стартовую позицию Саши $$$P_S$$$, определите, кто выигрывает в игре, если оба игрока пытаются победить.
Первая строка содержит одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора содержит целые числа $$$n$$$, $$$k$$$, $$$P_B$$$, $$$P_S$$$ ($$$1\le P_B,P_S\le n\le 2\cdot 10^5$$$, $$$1\le k\le 10^9$$$) — длина перестановки, продолжительность игры, стартовые позиции соответственно.
Следующая строка содержит $$$n$$$ целых чисел $$$p_1,\dots,p_n$$$ ($$$1 \le p_i \le n$$$) — элементы перестановки $$$p$$$.
Следующая строка содержит $$$n$$$ целых чисел $$$a_1,\dots,a_n$$$ ($$$1\le a_i\le 10^9$$$) — элементы массива $$$a$$$.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите:
104 2 3 24 1 2 37 2 5 610 8 2 103 1 4 5 2 7 8 10 6 95 10 5 1 3 7 10 15 4 32 1000000000 1 21 24 48 10 4 15 1 4 3 2 8 6 71 1 2 1 2 100 101 1025 1 2 51 2 4 5 34 6 9 4 24 2 3 14 1 3 26 8 5 36 9 5 46 1 3 5 2 46 9 8 9 5 104 8 4 22 3 4 15 2 8 74 2 3 14 1 3 26 8 5 32 1000000000 1 21 21000000000 2
Bodya Sasha Draw Draw Bodya Sasha Sasha Sasha Sasha Bodya
Ниже вы можете найти объяснение для первого набора входных данных, где игра состоит из $$$k=2$$$ ходов.
Ход | Позиция Боди | Очки Боди | Ход Боди | Позиция Саши | Очки Саши | Ход Саши |
первый | $$$3$$$ | $$$0 + a_3 = 0 + 5 = 5$$$ | остаётся в текущей позиции | $$$2$$$ | $$$0 + a_2 = 0 + 2 = 2$$$ | переходит в $$$p_2=1$$$ |
второй | $$$3$$$ | $$$5 + a_3 = 5 + 5 = 10$$$ | остаётся в текущей позиции | $$$1$$$ | $$$2 + a_1 = 2 + 7 = 9$$$ | остаётся в текущей позиции |
конечный результат | $$$3$$$ | $$$10$$$ | $$$1$$$ | $$$9$$$ |
Как мы видим, счет Боди больше, поэтому он выигрывает игру. Можно показать, что Бодя всегда может выиграть эту игру.
Название |
---|