B - Restore the Permutation by Merger

問題

https://codeforces.com/contest/1385/problem/B (新しいタブで開く)

問題文

$1, \cdots, n$ の順列を考える。
これの順序を変えずに、その順列に挿入して、$2n$ 要素からなる数列を作る。

同じ順列 $p, p'$ を用意して、$0 \le i_1 \le i_2 \le \cdots \le i_n \le n$ を選んで、 $p'_j$ を $p_{i_j}$ と $p_{i_j+1}$ の間に挿入する。
みたいな感じ (語彙力)

例えば、 $\left[ 3, 1, 2 \right]$ から $\left[ 3,1,2,3,1,2 \right], \left[ 3,3,1,1,2,2 \right], \left[ 3,1,3,1,2,2 \right]$ などが作れる。

元の順列を復元してね。

制約

• $1 \le t \le 400$
• $1 \le n \le 50$

サンプル

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

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

考察

実は単純に 1 回目に出てきた要素をそのまま使えば OK。

コード

https://codeforces.com/contest/1385/submission/126229495 (新しいタブで開く)

void solve() {
  int n;
  cin >> n;
  vector<bool> seen(n, false);
  rep(i, 2 * n) {
    int p;
    cin >> p;
    if (!seen[p - 1]) {
      cout << p << " ";
      seen[p - 1] = true;
    }
  }
  cout << endl;
}