問題
https://codeforces.com/contest/1512/problem/D (新しいタブで開く)
問題文
以下のように構築された、長さ の 数列 が与えられる。
- 長さ の数列 を考える。
- とする。
- とする。
- となる を選び、 とする。
- をシャッフルする。
元の数列 としてあり得るのは?
制約
- の総和は を超えない
サンプル
4 3 2 3 7 12 2 4 9 1 7 1 6 5 5 18 2 2 3 2 9 2 3 2 6 9 2 1
2 3 7 -1 2 2 2 3 9 1 2 6
考察
条件を満たす が構築できればいいので、要は を求める問題。
制約から、 が成り立ってるはずなので、 が成り立つ。
まずソートして、 とする。
パターンとしては、以下の 2 パターンがあり得る。
前者の場合、 になる。
あとは、 になるので、これが存在するかチェックすればいい。
後者の場合、 になるので、これが成り立っているかチェックする。
両方成り立たないなら -1
。
あとは に気を付けて、出力すればいい。
コード
https://codeforces.com/contest/1512/submission/125541260 (新しいタブで開く)
void solve() { ll n; cin >> n; vector<ll> b(n + 2), sum(n + 3, 0); rep(i, n + 2) cin >> b[i]; sort(b.begin(), b.end()); rep(i, n + 2) sum[i + 1] = b[i] + sum[i]; ll x = 0; ll su = b[n + 1]; const ll del = sum[n + 1] - b[n + 1]; rep(i, n + 1) { if (b[i] == del) x = b[i]; } if (!x) { if (sum[n] == b[n]) { su = b[n]; x = b[n + 1]; } else { cout << -1 << endl; return; } } bool remX = false; bool remS = false; rep(i, n + 2) { if (!remX && b[i] == x) { remX = true; } else if (!remS && b[i] == su) { remS = true; } else { cout << b[i] << " "; } } cout << endl; }