D.Corrupted Array

• Quiz
  • https://codeforces.com/contest/1512/problem/D
• AC
  • https://codeforces.com/contest/1512/submission/113376076
• 解説
  • editorialと違う解法だったので書いておく
  • Aの和はどれだろうか？
  • Bを昇順ソートして、Aの和はBの最後端か、その手前に限られる
  • その2パターンをチェックすればいい

void solve(){
  ll N;cin>>N;
  VI A(N+2);
  rep(i, N+2)cin >> A[i];
  SORT(A);

  // 和がA[N]の場合
  {
    ll sum=0;
    rep(i,N)sum+=A[i];
    if(sum==A[N]){
      // found!
      VI Ans;
      rep(i,N)Ans.push_back(A[i]);
      print_vector(Ans);return;
    }
  }

  // 和がA[N+1]の場合
  {
    ll sum=0;
    rep(i,N+1)sum+=A[i];

    ll ma = A.back();

    // i番目を除去したときに、和と一致するかチェック
    rep(i,N+1){
      if(sum-A[i]==ma){
        // found!

        // i以外が答え
        VI Ans;
        rep(j,N+1){
          if(i==j)continue;
          Ans.push_back(A[j]);
        }
        print_vector(Ans);return;
      }
    }
  }
  p(-1);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N;cin>>N;
    while(N--)solve();
    
    return 0;
}