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