B - Restore the Permutation by Merger

cpcodeforcesdiv3greedy

最終更新日

Table of Contents

Loading...

問題

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