Codeforces Round ＃803 (Div. 2) C. 3SUM Closure

C 3SUM Closure

The question

Give a sequence , Ask whether the sum of three arbitrary numbers is also in this sequence

Cause of error

 -3 -1 1 1 Not discussed , Can't discuss , So it should be direct brute force, No classified discussion

analysis

This problem has many boundaries when the data is relatively small , However, when there is a small amount of data, we can directly triple cycle violence

So we only need to consider the case that the amount of data is large enough .
We put All the data are calculated violently .

We record the number of all positive and negative numbers in the sequence .

Positive or negative numbers exceed 2 It's definitely not possible

Positive and negative numbers each have an hour , They must be opposite to each other to satisfy the condition .

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
bool cabs(int x, int y){
	return abs(x) > abs(y);
}	
int a[2000009];
int main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
 	cin >> t;
 	while(t -- ) {
 		int n, c = 0, c2 = 0;
 		cin >> n;
 		for (int i = 0; i < n; i ++ ) {
 			cin >> a[i];
 			c += a[i] > 0;
 			c2 += a[i] < 0;
 		}
 		if(c > 2 || c2 > 2) {
 			cout << "no\n";
 			continue;
 		}
 		sort(a, a + n, cabs);// Quintessential operation , Show 
 		n = min(n, 9);
 		sort(a, a + n);
		bool tag = true;
		for (int i = 0; i < n; i ++ ) {
			for (int j = i + 1; j < n; j ++ ) {
				for (int k = j + 1; k < n; k ++ ) {
					int w = a[i] + a[j] + a[k];// This place has to think of using binary search , Or use map And other ways to reduce the search complexity 
					int nx = lower_bound(a, a + n, w) - a;
					if(nx == n || a[nx] != w) {
						tag = false;
					}
				}
			}
 		}
 		if(tag)cout << "yes\n";
 		else cout << "no\n";
 	}
	return 0;
}

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

int main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 	int t;
 	cin >> t;
 	while(t -- ) {
 		int n, sum = 0;
 		int cnt[2] = {0, 0};
 		cin >> n;
		std::vector<int> a(n);
		for (int i = 0; i < n; i ++ ) {
			cin >> a[i];
			cnt[0] += a[i] > 0;
			cnt[1] += a[i] < 0;
			sum += a[i];
		}
 		if(n <= 10) {
 			set<int> s;
			for (int i = 0; i < n; i ++ )s.insert(a[i]);
 			bool ok = true;
 			for (int i = 0; i < n; i ++ ) {
 				for (int j = i + 1; j < n; j ++) {
 					for (int k = j + 1; k < n; k ++ ) {
 						if(!s.count(a[i] + a[j] + a[k])) {
 							ok = false;
 						}
 					}
 				}
 			}
 			if(ok) cout << "yes\n";
 			else cout << "no\n";
 		}
 		else {
 			if(cnt[0] + cnt[1] == 1) cout << "yes\n";
 			else if(cnt[0] > 1 || cnt[1] > 1 || sum) cout << "no\n";
 			else cout << "yes\n";
 		}
 	}   
	return 0;
}