B - Restore the Permutation by Merger

cpcodeforcesdiv3greedy

最終更新日

問題

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

問題文

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

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

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

元の順列を復元してね。

制約

サンプル

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;
}