A16683 | $Cycle Sort$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定两个整数数组 $a_0, \ldots, a_{n - 1}$ 和 $b_0, \ldots, b_{m - 1}$。在 $a_0, \ldots, a_{n - 1}, b_0, \ldots, b_{m - 1}$ 这 $n+m$ 个数中，$1$ 到 $n+m$ 的每个整数各出现恰好一次。 我们对这两个数组进行 $k$ 次操作。具体地，对于每个整数 $i$，从 $0$ 到 $k-1$ 依次进行以下操作： - 如果 $a_{i \bmod n} > b_{i \bmod m}$，则交换 $a_{i \bmod n}$ 和 $b_{i \bmod m}$； - 否则，不进行操作。 请你在 $k$ 次操作全部完成后，输出两个数组的最终状态。

每组测试数据包含多个测试用例。第一行包含测试用例的个数 $t$（$1 \le t \le 10^4$）。每组测试用例描述如下。 每个测试用例第一行包含三个整数 $n, m, k$（$1 \leq n, m \leq 2 \cdot 10^5$，$0 \leq k \leq 10^{18}$）。 第二行包含 $n$ 个整数 $a_0, \ldots, a_{n-1}$。 第三行包含 $m$ 个整数 $b_0, \ldots, b_{m-1}$。 保证 $a_0, \ldots, a_{n-1}, b_0, \ldots, b_{m-1}$ 联合起来是 $1$ 到 $n+m$ 的一个排列。 所有测试用例中 $n+m$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试用例，输出两行，分别为 $k$ 次操作之后数组 $a_0, \ldots, a_{n-1}$ 和 $b_0, \ldots, b_{m-1}$ 的状态。

输入 #1

输出 #1

C++ 编辑器

输入

输出