AT_utpc2025_a.Apparently Make UTPC

NOI/NOI+/CTSC

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

给定三个长度分别为 X,Y,ZX, Y, Z 的正整数数列 A=(A1,A2,…,AX)A = (A_1, A_2, \ldots, A_X),B=(B1,B2,…,BY)B = (B_1, B_2, \ldots, B_Y),C=(C1,C2,…,CZ)C = (C_1, C_2, \ldots, C_Z)。保证满足 X≤Y≤ZX \leq Y \leq Z。

你可以自由地对 CC 中的元素进行重新排列,目标是使重排后的 CC 同时包含 AA 和 BB 作为其连续子序列(连续子串)。

请判断能否达成该目标。如果能达成,请输出所有满足条件的重排结果中,字典序最小的那个数列 CC。

本题包含 TT 个测试用例,请分别给出答案。

输入格式

输入由标准输入给出,格式如下:

第一行包含一个整数 TT,表示测试用例组数;

接下来依次给出 TT 个测试用例:

每个测试用例的第一行为三个整数 X,Y,ZX, Y, Z;

第二行为数列 AA 的元素:A1,A2,…,AXA_1, A_2, \ldots, A_X;

第三行为数列 BB 的元素:B1,B2,…,BYB_1, B_2, \ldots, B_Y;

第四行为数列 CC 的元素:C1,C2,…,CZC_1, C_2, \ldots, C_Z。

输出格式

输出共 TT 行。

第 ii 行输出第 ii 个测试用例的答案:如果无法达成目标,输出 -1;如果可以达成,输出重排后满足条件且字典序最小的数列 CC(元素之间用空格隔开)。

输入输出样例

  • 输入#1

    3
    2 2 4
    4 3
    2 1
    4 3 2 1
    2 3 4
    4 3
    3 2 1
    4 3 2 1
    3 3 3
    1 1 1
    2 2 2
    3 3 3

    输出#1

    2 1 4 3
    4 3 2 1
    -1

说明/提示

样例解释 1

  • 对于第 11 个测试用例,重排后满足条件的 CC 有两种可能:(2,1,4,3)(2, 1, 4, 3) 和 (4,3,2,1)(4, 3, 2, 1)。其中 (2,1,4,3)(2, 1, 4, 3) 的字典序更小,因此输出它。
  • 对于第 22 个测试用例,重排后满足条件的 CC 只有 (4,3,2,1)(4, 3, 2, 1) 这 11 种可能,因此输出它。
  • 对于第 33 个测试用例,无论怎么重排都无法同时包含 AA 和 BB,因此输出 -1。

数据范围

  • 输入数据全为整数
  • 1≤T≤1051 \leq T \leq 10^5
  • 1≤X≤Y≤Z≤2×1051 \leq X \leq Y \leq Z \leq 2 \times 10^5
  • 1≤Ai≤Z1 \leq A_i \leq Z
  • 1≤Bi≤Z1 \leq B_i \leq Z
  • 1≤Ci≤Z1 \leq C_i \leq Z
  • 在同一个测试文件中,所有测试用例的 X+Y+ZX + Y + Z 之和不超过 4×1054 \times 10^5。

输入解题思路,AI测评打分。不知道怎么写?

首页