[7453] 합이 0인 네 정수

https://www.acmicpc.net/problem/7453

7453번: 합이 0인 네 정수

O(N^4)는 시간 초과가 나오지만, O(2*(N^2))은 통과할 수 있는 수준이다.

'중간에서 만나기'와 비슷한 방식으로, 4개의 집합 A, B, C, D를 2개의 집합 A+B, C+D로 나누어 투포인터를 할 수 있다.

다른 방법으로는 A+B에서 나올 수 있는 값을 전부 저장해두고 C와 D의 2중 루프에서 -(c+d)를 이분탐색할 수 있다.

모든 경우의 수를 탐색하기 위해서, -(c+d)가 존재하는 여부뿐 아니라, -(c+d)의 개수 또한 구해야 하는데

s = lower_bound();
e = upper_bound();

일때 -(c+d)는 구간 [s, e)에 대해서 존재한다. 그렇기에 e-s를 정답으로 누적해주면 된다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

int n;

ll ans;

vector<int> v[4];

vector<int> c;

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n;

    int i, j;

    for (i = 0; i < 4; i++) v[i].resize(n);

    for (i = 0; i < n; i++)

        for (j = 0; j < 4; j++) cin >> v[j][i];

    for (i = 0; i < n; i++)

        for (j = 0; j < n; j++) c.push_back(v[0][i] + v[1][j]);

    sort(c.begin(), c.end());

    for (i = 0; i < n; i++) {

        for (j = 0; j < n; j++) {

            int l = lower_bound(c.begin(), c.end(), -(v[2][i] + v[3][j])) -

                    c.begin();

            int r = upper_bound(c.begin(), c.end(), -(v[2][i] + v[3][j])) -

                    c.begin();

            if (c[l] + v[2][i] + v[3][j] == 0) ans += ((ll)r - (ll)l);

        }

    }

    cout << ans;

    return 0;

}

---