被盗的项链AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)There are $2N$ gems arranged in a row from left to right, and the type of the $i$-th gem from the left is $A_i$. Here, $A_i$ is an integer between $1$ and $N$, inclusive, and there are exactly two gems of each type.
有 $2N$ 颗宝石从左到右排成一行,从左往右第 $i$ 颗宝石的类型为 $A_i$。其中,$A_i$ 是一个介于 $1$ 和 $N$ 之间(含)的整数,并且每种类型恰好有两颗宝石。AI (CI翻译)
You want to insert dividers satisfying the following conditions.
你想插入若干隔板,使其满足以下条件。AI (CI翻译)
- Each divider's position is represented by an integer
$i$($1 \le i \le 2N - 1$), meaning it divides between the$i$-th and$(i+1)$-th gems from the left. - No two or more dividers exist at the same position.
- The number of dividers
$K$is at most$N$. - Inserting
$K$dividers divides the row of gems into$K + 1$segments. Here, collecting all gems in the odd-numbered (first, third, ...) segments from the left yields exactly one gem of each type$1, 2, \ldots, N$.
- 每块隔板的位置用整数
$i$($1 \le i \le 2N - 1$)表示,意为隔板插在从左往右第$i$颗和第$(i+1)$颗宝石之间。 - 同一位置不能插入多块隔板。
- 隔板数量
$K$不超过$N$。 - 插入
$K$块隔板后,宝石行会被分成$K + 1$段。将从左往右编号为奇数(第一段、第三段等)的段中的所有宝石收集起来后,恰好得到类型$1, 2, \ldots, N$各一颗宝石。
Output one way to insert dividers satisfying this condition. It can be proved that such a way always exists.
请输出一种满足条件的插入隔板方案。可以证明,这样的方案总是存在。AI (CI翻译)
You are given $T$ test cases; solve each one.
给定 $T$ 组测试用例,请分别求解。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$1 \le T \le 10^5$$1 \le N \le 2 \times 10^5$$1 \le A_i \le N$($1 \le i \leq 2N$)- There are exactly two gems of each type. That is, for each
$x$($1 \le x \le N$), there are exactly two indices$i$with$A_i = x$. - The sum of
$N$over all test cases is at most$2 \times 10^5$. - All input values are integers.
$1 \le T \le 10^5$$1 \le N \le 2 \times 10^5$$1 \le A_i \le N$($1 \le i \leq 2N$)- 每种类型的宝石恰好有两颗。也就是说,对每个
$x$($1 \le x \le N$),恰有两个下标$i$满足$A_i = x$。 - 所有测试用例的
$N$之和不超过$2 \times 10^5$。 - 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入中给出,格式如下:AI (CI翻译)
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_TAI (CI翻译)
Each test case is given in the following format:
每组测试用例的格式如下:AI (CI翻译)
N
A_1 A_2 \ldots A_{2N}
N
A_1 A_2 \ldots A_{2N}AI (CI翻译)
Output
输出格式
AI (CI翻译)Output for the $T$ test cases in order.
按顺序输出 $T$ 组测试用例的答案。AI (CI翻译)
For each test case, output a way to insert dividers satisfying the condition. Specifically, let $K$ be the number of dividers and $C_1, C_2, \ldots, C_K$ be the positions of the dividers in ascending order, and output in the following format:
对于每组测试用例,输出一种满足条件的隔板插入方案。具体来说,设 $K$ 为隔板数量,$C_1, C_2, \ldots, C_K$ 为隔板位置,且按升序排列,按以下格式输出:AI (CI翻译)
K
C_1 C_2 \ldots C_K
K
C_1 C_2 \ldots C_KAI (CI翻译)
Here, $K$ must be at most $N$.
其中,$K$ 必须不超过 $N$。AI (CI翻译)
样例
2
3
1 2 2 3 3 1
5
1 2 3 4 5 5 4 3 2 1
3
1 2 4
1
5
题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(gpt-6.1-sol),如有出入请以原文为准。