/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
2N 個の宝石が左右一列に並んでおり、左から i 番目の宝石の種類は A_i です。ここで、 A_i は 1 以上 N 以下の整数であり、どの種類の宝石も 2 つずつ存在します。
ここに以下の条件を満たすように仕切りを入れたいです。
- それぞれの仕切りの位置は整数 i (1 \le i \le 2N - 1) により表され、左から i 番目の宝石と i + 1 番目の宝石の間を仕切ることを意味する。
- 同じ位置に 2 つ以上の仕切りは存在しない。
- 仕切りの個数 K は N 以下である。
- 仕切りを K 個入れることにより、宝石の列は K + 1 個の区間に分かれる。このとき、左から奇数番目の区間にある宝石をすべて集めると、種類 1,2,\ldots,N の宝石がちょうど 1 つずつ得られる。
この条件を満たすように仕切りを入れる方法を 1 つ出力してください。ただし、このような方法が必ず存在することが証明できます。
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)
- どの種類の宝石も 2 つずつ存在する、つまり各 x (1 \le x \le N) について、A_i = x なる i はちょうど 2 つ
- 全てのテストケースにおける 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 つ目のテストケースについては、位置 1,2,4 で仕切ることによって、宝石は (1),(2),(2,3),(3,1) のように区間に分かれ、左から奇数番目の区間にある宝石をすべて集めると、種類 1,2,3 の宝石がちょうど 1 つずつ得られます。
Score : 500 points
Problem Statement
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.
You want to insert dividers satisfying the following conditions.
- 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.
Output one way to insert dividers satisfying this condition. It can be proved that such a way always exists.
You are given T test cases; solve each one.
Constraints
- 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.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N
A_1 A_2 \ldots A_{2N}
Output
Output for the T test cases in order.
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
Here, K must be at most N.
Sample Input 1
2 3 1 2 2 3 3 1 5 1 2 3 4 5 5 4 3 2 1
Sample 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.