B. Restore the Permutation by Merger (Codeforces Round #656 Div. 3)

問題

https://codeforces.com/contest/1385/problem/B

問題概要

長さnの順列2つを、それぞれの順番が壊れないようにマージさせた長さ2nの数列が与えられる。

たとえば元の順列が[3, 1, 2]のとき、[3, 1, 2, 3, 1, 2]、[3, 3, 1, 1, 2, 2]そして[3, 1, 3, 1, 2, 2]などは与えられる数列としてありうる。

一方、[1, 3, 2, 1, 2, 3]、[3, 1, 2, 3, 2, 1]、[3, 3, 1, 2, 2, 1]などは順番を入れ替えずに[3, 1, 2]を2つ復元することができないため、与えられる数列としてありえない。

さて、長さ2nの数列から元の順列を復元せよ。

考察

順列なので同じ数字は1つ（与えられた数列は2つの順列をマージしているので2つ）しか現れず、順番も入れ替えが行われていないことが保証されているため、1からnまでのそれぞれの数字が最初に登場した順に並べれば、それが答えとなります。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> ans;
        vector<bool> used(n + 1, false);
        int a;
        for (int i = 0; i < n * 2; i++) {
            cin >> a;
            if (used[a]) continue;
            ans.emplace_back(a);
            used[a] = true;
        }
        for (int i = 0; i < n; i++) cout << ans[i] << " ";
        cout << endl;
    }
}