AT_abc306_c [ABC306C] Centers

题目描述

给定一个长度为 $3N$ 的数列 $A=(A_1,A_2,\dots,A_{3N})$，其中 $1,2,\dots,N$ 每个数字恰好出现 $3$ 次。

对于 $i=1,2,\dots,N$，定义 $f(i)$ 为 $A$ 中数字 $i$ 出现的三个位置中间的那个位置的下标。请将 $1,2,\dots,N$ 按照 $f(i)$ 的升序重新排列并输出。

$f(i)$ 的严格定义如下：

• 设 $A_j = i$ 的所有 $j$ 为 $j = \alpha, \beta, \gamma$，且 $\alpha < \beta < \gamma$，则 $f(i) = \beta$。

输入格式

输入以如下格式从标准输入给出。

$N$ $A_1$ $A_2$ $\dots$ $A_{3N}$

输出格式

请输出将 $1,2,\dots,N$ 按照 $f(i)$ 的升序排列后得到的长度为 $N$ 的数列，数之间用空格隔开。

输入输出样例 #1

输入 #1

3
1 1 3 2 3 2 2 3 1

输出 #1

1 3 2

输入输出样例 #2

输入 #2

1
1 1 1

输出 #2

1

输入输出样例 #3

输入 #3

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

输出 #3

3 4 1 2

说明/提示

限制条件

• $1 \leq N \leq 10^5$
• $1 \leq A_j \leq N$
• 对于每个 $i=1,2,\dots,N$，$A$ 中的 $i$ 恰好出现 $3$ 次
• 所有输入均为整数

样例解释 1

• $A$ 中 $1$ 出现在 $A_1,A_2,A_9$，因此 $f(1)=2$。
• $A$ 中 $2$ 出现在 $A_4,A_6,A_7$，因此 $f(2)=6$。
• $A$ 中 $3$ 出现在 $A_3,A_5,A_8$，因此 $f(3)=5$。 因此，$f(1)<f(3)<f(2)$，所以输出顺序为 $1,3,2$。

由 ChatGPT 4.1 翻译