← 返回题目列表

AtCoder · arc215_b

B. 被盗的项链

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有 2N 宝石从左到右排列成一排,以及宝石的类型 i左边第一个宝石是 A_i。在这里, A_i 是介于 1 和 N,包含在内,并且每种类型恰好有两颗宝石。

您想要插入满足以下条件的分隔线。

  • 每个分隔符的位置由一个整数表示 i (1 \le i \le 2N - 1),这意味着它在 i-th 和 (i+1)左起第 颗宝石。
  • 同一位置不存在两个或多个分隔线。
  • 分隔线数量 K 最多是 N.
  • 插入 K 分隔线将宝石行分为 K + 1 段。在这里,收集左侧奇数(第一、第三……)段中的所有宝石会产生每种类型的恰好一个宝石 1, 2, \ldots, N.

输出一种插入满足此条件的分隔符的方式。可以证明这样的方式总是存在的。

你被给予 T 测试用例;逐一解决。

约束

  • 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.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

每个测试用例均按以下格式给出:

N
A_1 A_2 \ldots A_{2N}

输出

输出 T 测试用例按顺序排列。

对于每个测试用例,输出一种插入满足条件的分隔符的方法。 具体来说,让 K 是分隔线的数量, C_1, C_2, \ldots, C_K 为分隔符的位置,按升序排列,并按以下格式输出:

K
C_1 C_2 \ldots C_K

在这里, K 最多必须是 N.


样本输入 1

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

示例输出 1

3
1 2 4
1
5

对于第一个测试用例,在位置插入分隔符 1, 2, 4 将宝石分成几段 (1),(2),(2,3),(3,1),并收集左侧奇数段中的所有宝石,每种类型恰好产生一颗宝石 1, 2, 3.