CF618F Double Knapsack

给定两个多重集 $A$ 和 $B$，每个多重集中恰好有 $n$ 个整数，每个整数都在 $1$ 到 $n$ 之间（包含 $1$ 和 $n$）。多重集允许相同元素出现多次。 你需要找到 $A$ 的一个非空子集和 $B$ 的一个非空子集，使得这两个子集中元素的和相等。子集同样作为多重集处理，即可以包含重复元素。 如果不存在这样的情况，输出 $-1$。否则，输出 $A$ 和 $B$ 中满足条件的任意一组子集对应的元素下标。

输入的第一行包含一个整数 $n$（$1 \leq n \leq 1000000$），表示两个多重集的大小。 第二行包含 $n$ 个整数，表示多重集 $A$ 的元素。每个元素都在 $1$ 到 $n$ 之间（包含 $1$ 和 $n$）。 第三行包含 $n$ 个整数，表示多重集 $B$ 的元素。每个元素都在 $1$ 到 $n$ 之间（包含 $1$ 和 $n$）。

如果无解，输出一个整数 $-1$。否则，按照下面的格式输出你的答案，共四行。 第一行输出 $k_a$，表示所选 $A$ 子集的大小。 第二行输出 $k_a$ 个互不相同的整数，表示 $A$ 子集中元素的下标。 第三行输出 $k_b$，表示所选 $B$ 子集的大小。 第四行输出 $k_b$ 个互不相同的整数，表示 $B$ 子集中元素的下标。 两个集合的元素编号均从 $1$ 到 $n$。如果有多组解，输出任意一组即可。

由 ChatGPT 5 翻译