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

해결

A,B,C,D 하나씩 순회해가며 찾기엔 4000개씩 4번... $4000^4$,, 안된다.

• A+B 한 그룹, C+D 한 그룹 해서 두 그룹으로 나눠서 $4000^2$개인 두 그룹으로 만들었다.
  A+B+C+D 네개 다 더해서 0 == (A+B) + (C+D) 두개 더해서 0
• 두 그룹의 원소를 하나씩 더하면서 찾기보다 정렬 후 이분탐색을 진행했다.
  • (A + B) = -(C + D) 이어야 하므로, CD 그룹에서 이를 만족하는 원소를 찾았다.
• 개수를 구하는 것이므로 upper bound와 lower bound를 사용했다.
  • ⭐️정렬 이후에는 중복된 데이터가 뭉쳐있게 된다!
  • ⭐️upper에서 lower를 빼면, 중복된 데이터 개수를 쉽게 카운트 할 수 있다.

소스코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long

vector<int> A;
vector<int> B;
vector<int> C;
vector<int> D;
vector<int> AB;
vector<int> CD;

int n;
ll ans;

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

  cin>>n;
  for(int i = 0; i<n; i++){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    A.push_back(a);
    B.push_back(b);
    C.push_back(c);
    D.push_back(d);
  }

  for(int i = 0; i<n; i++){
    for(int j = 0; j<n; j++){
      AB.push_back(A[i]+B[j]); //a+b
      CD.push_back((C[i]+D[j])*-1); //-(c+d)
    }
  }

  sort(AB.begin(),AB.end());
  sort(CD.begin(),CD.end());

  ll size = AB.size();
  for(ll i = 0; i<size; i++){
    ll lower = lower_bound(CD.begin(),CD.end(),AB[i])-CD.begin();    
    ll upper = upper_bound(CD.begin(),CD.end(),AB[i])-CD.begin();
    ans += (upper-lower);
  }
  cout<<ans;
}

제출결과

틀렸을 땐 당황했으나 int를 long long으로 바꾸고 해결.. 헤헤