AtCoder Regular Contest 215
B
被盗的项链
Stolen Necklace
AtCoder
⌀ 1216
原题
← AC →

被盗的项链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$ 各一颗宝石。
AI (CI翻译)

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$。
  • 所有输入值均为整数。
AI (CI翻译)

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}_T
AI (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_K
AI (CI翻译)

Here, $K$ must be at most $N$.

其中,$K$ 必须不超过 $N$。AI (CI翻译)

样例

Input #1
2
3
1 2 2 3 3 1
5
1 2 3 4 5 5 4 3 2 1
Output #1
3
1 2 4
1
5
For the first test case, inserting dividers at positions $1, 2, 4$ divides the gems into segments $(1),(2),(2,3),(3,1)$, and collecting all gems in the odd-numbered segments from the left yields exactly one gem of each type $1, 2, 3$.
题目信息
题号
arc215_b
时间限制
2 s
内存限制
1024 MB

题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(gpt-6.1-sol),如有出入请以原文为准。