백준 BOJ 7453 - 합이 0인 네 정수

어째 구데기만 골라풀고있는거같은 느낌이 든다....

 

이번에는 map을 사용하거나 unordered_map을 사용하면 TLE를 받는 문제다.

답은 벡터를 정렬해서 이분탐색.

 

답을 안까보면 이런건 모르잖아요 ㅠㅠㅠㅠㅠ

 

코드포스에서 hack할때 map을 자주 이용한다고 들었는데

이걸 당할줄은 몰랐다;;

 

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

7453번: 합이 0인 네 정수

4000^4 는 TLE가 나게 될 것이므로

4000^2의 갯수를 가지는

두개의 벡터를 만들어서

하나의 벡터를 정렬 후

그 정렬된 벡터를 이분탐색해주면

시간복잡도는

O((N^2)log(N^2)) 되시겠다.

 

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

vector<int> v1;
vector<int> v2;

int a[4567];
int b[4567];
int c[4567];
int d[4567];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n;
	cin >> n;
	for(int i=0; i<n; i++) cin >> a[i] >> b[i] >> c[i] >> d[i];
	
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			v1.push_back(a[i]+b[j]);
			v2.push_back(c[i]+d[j]);
		}
	}
	
	sort(v2.begin(), v2.end());
	
	long long int ans = 0;
	for(int i=0; i<v1.size(); i++){
		auto s = lower_bound(v2.begin(), v2.end(), -v1[i]);
		auto e = upper_bound(v2.begin(), v2.end(), -v1[i]);
		
		if(*s == -v1[i]) ans += e-s;
	}
	cout << ans;
	return 0;
}