Centers

题目描述

你被给定一个长度为 $3N$ 的序列 $A=(A_1,A_2,\dots,A_{3N})$，其中每个 $1,2,\dots,$ 和 $N$ 恰好出现三次。 对于 $i=1,2,\dots,N$，令 $f(i)$ 为数字 $i$ 在 $A$ 中中间一次出现的位置下标。 按 $f(i)$ 的升序对 $1,2,\dots,N$ 进行排序。 形式上，$f(i)$ 定义如下。

假设满足 $A_j = i$ 的那些 $j$ 为 $j=\alpha,\beta,\gamma\ (\alpha < \beta < \gamma)$。那么，$f(i) = \beta$。

输入格式

输入从标准输入按如下格式给出： $N$ $A_1$ $A_2$ $\dots$ $A_{3N}$

输出格式

输出长度为 $N$ 的序列，该序列是将 $1,2,\dots,N$ 按 $f(i)$ 的升序排列所得，元素之间用空格分隔。

3
1 1 3 2 3 2 2 3 1

1 3 2

1
1 1 1

1

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

3 4 1 2

提示

$1\leq N \leq 10^5$ $1 \leq A_j \leq N$ $i$ 在序列 $A$ 中恰好出现三次，对每个 $i=1,2,\dots,N$ 都如此。 所有输入值均为整数。$1$ 在序列 $A$ 的 $A_1,A_2,A_9$ 处出现，所以 $f(1) = 2$。 $2$ 在序列 $A$ 的 $A_4,A_6,A_7$ 处出现，所以 $f(2) = 6$。 $3$ 在序列 $A$ 的 $A_3,A_5,A_8$ 处出现，所以 $f(3) = 5$。

因此，f(1) < f(3) < f(2)，所以应当以此顺序打印 $1,3$ 和 $2$。

标签: AtCoder|abc306C

来源

AtCoder|abc306C