CFCF2192E.Swap to Rearrange
提高+/省选-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
给定两个长度为 n 的数组 a 和 b。你可以进行如下操作:
- 选择一个下标 i(1≤i≤n),将 ai 和 bi 交换。
你可以进行任意次数的操作(也可以一次都不做),但每个下标最多只能被选择一次。你的任务是,在所有操作完成后,使得 a 成为 b 的一个重排列,或者说明这不可能做到。你不需要最小化操作次数。
输入格式
每组测试数据包含多个测试用例。第一行包含测试用例数 t(1≤t≤104)。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数 n(1≤n≤106)。
第二行包含 n 个整数 a1,a2,…,an(1≤ai≤n)。
第三行包含 n 个整数 b1,b2,…,bn(1≤bi≤n)。
保证所有测试用例中 n 的总和不超过 106。
输出格式
对于每个测试用例,若无法使 a 成为 b 的一个重排列,则输出 −1。否则,按如下格式输出两行:
- 第一行输出操作次数 s(0≤s≤n)。
- 第二行输出 s 个数,依次为每次操作所选择的下标。
要求每个下标最多被选择一次。
若存在多种可行方案,可以输出任意一种。
输入输出样例
输入#1
4 4 1 1 3 3 2 2 4 4 3 1 2 1 3 3 1 3 1 2 3 2 3 1 4 1 2 2 4 3 1 4 3
输出#1
2 2 4 -1 0 2 3 4
说明/提示
在第一个测试用例中,进行了 swap(a2,b2) 和 swap(a4,b4) 操作,使得 a=[1,2,3,4],b=[2,1,4,3]。此时 a 可以通过重排 b 得到。
在第二个测试用例中,无论如何操作,都无法使 a 成为 b 的一个重排列。