Codeforces #1512D Corrupted Array

문제

https://codeforces.com/problemset/problem/1512/D

걸린 시간

00 : 32 : 38 실패

풀이

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;
        vector<int> b(n+2);
        for(auto& i : b) cin >> i;
        sort(all(b));
        vector<ll> pS(n+2);
        pS[0] = b[0];
        for(int i = 1; i < n+2; i++){
            pS[i] = pS[i-1] + b[i];
        }
        vector<int> a;
        for(int i = 0; i < n+2; i++){
            int idx;
            int maxi;
            ll s;
            if(i == n+1){
                idx = n;
                s = pS[idx-1];
            }
            else{
                idx = n+1;
                s = pS[idx-1]-b[i];
            }
            maxi = b[idx];
            if(s == maxi){
                for(int j = 0; j < n+2; j++){
                    if(j == i || j == idx) continue;
                    a.push_back(b[j]);
                }
                break;
            }
        }
        if(a.size() == 0) cout << -1;
        else for(int x : a) cout << x << " ";
        cout << "\n";
    }
    return 0;
}

div.3 D 번 문제로 A~C 구현 문제에서 시간을 너무 사용하는 바람에 풀지 못했었다.

배열을 정렬한 후 구간합을 구한 뒤, 순서대로 현재 값이 x 일 때를 가정하여 계산해보면 시간안에 답을 구할 수 있다.

어렵지 않은 문제였는데 업솔빙을 하면서도 구현에서 실수가 하나 있었다. 빠르고 정확하게 구현하는 연습을 많이 해야할 것 같다.