803_Div3(3SUM Closure)

C. 3SUM Closure

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array 𝑎a of length 𝑛n. The array is called 3SUM-closed if for all distinct indices 𝑖i, 𝑗j, 𝑘k, the sum 𝑎𝑖+𝑎𝑗+𝑎𝑘ai+aj+ak is an element of the array. More formally, 𝑎a is 3SUM-closed if for all integers 1≤𝑖<𝑗<𝑘≤𝑛1≤i<j<k≤n, there exists some integer 1≤𝑙≤𝑛1≤l≤n such that 𝑎𝑖+𝑎𝑗+𝑎𝑘=𝑎𝑙ai+aj+ak=al.

Determine if 𝑎a is 3SUM-closed.

Input

The first line contains an integer 𝑡t (1≤𝑡≤10001≤t≤1000) — the number of test cases.

The first line of each test case contains an integer 𝑛n (3≤𝑛≤2⋅1053≤n≤2⋅105) — the length of the array.

The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (−109≤𝑎𝑖≤109−109≤ai≤109) — the elements of the array.

It is guaranteed that the sum of 𝑛n across all test cases does not exceed 2⋅1052⋅105.

Output

For each test case, output "YES" (without quotes) if 𝑎a is 3SUM-closed and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).

Example

input

Copy

4
3
-1 0 1
5
1 -2 -2 1 -3
6
0 0 0 0 0 0
4
-1 2 -3 4

output

Copy

YES
NO
YES
NO

Note

In the first test case, there is only one triple where 𝑖=1i=1, 𝑗=2j=2, 𝑘=3k=3. In this case, 𝑎1+𝑎2+𝑎3=0a1+a2+a3=0, which is an element of the array (𝑎2=0a2=0), so the array is 3SUM-closed.

In the second test case, 𝑎1+𝑎4+𝑎5=−1a1+a4+a5=−1, which is not an element of the array. Therefore, the array is not 3SUM-closed.

In the third test case, 𝑎𝑖+𝑎𝑗+𝑎𝑘=0ai+aj+ak=0 for all distinct 𝑖i, 𝑗j, 𝑘k, and 00 is an element of the array, so the array is 3SUM-closed.

菜得离谱，理解错题意了：

要求是给你一个数组，求证数组中的任意三个元素之和在数组中存在这样一个数。

首先是如果有三个及以上的正数那么肯定存在三个最大的number之和大于数组中最大的元素，反之，如果三个为负的元素，最小的三个数的和也肯定比数组中最小的数小，不符合题意。

所以首先统计>0和<0的数量，如果有一个大于二， 就直接输出No就行

如果存在三个及以上的0， 和两个零的效果是一样的，所以复杂度是O(n+6^4) or O(n+6^3)

 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
 
using namespace std;
 
inline int read(){
	int res = 0 , flag = 1 ;
	char c = getchar() ;
	while(!isdigit(c)){
		if(c == '-') flag = -1 ;
		c = getchar() ;
	}
	while(isdigit(c)){
		res = (res << 1) + (res << 3) + (c ^ 48) ;
		c = getchar() ;
	}
	return res * flag ; 
}
 
void solved() {
	int n;
	int cnt1 = 0, cnt2 = 0;
	n = read();
	vector<int> arr1; // postive number
	vector<int> arr2; // negative number
	vector<int> a;
	for (int i = 0; i < n; i++) {
		int x;
		x = read();
		if (x > 0) arr1.push_back(x);
		if (x < 0) arr2.push_back(x);
		if (x == 0 && a.size() < 2) a.push_back(x);
	}
 
	if (arr1.size() > 2 || arr2.size() > 2) {
		cout << "No" << endl;
		return ;
	}
 
	for (auto i : arr1) a.push_back(i);
	for (auto i : arr2) a.push_back(i);
 
	for (int i = 0; i < a.size(); i++) {
		for (int j = i + 1; j < a.size(); j++) {
			for (int k = j + 1; k < a.size(); k++) {
				bool ok = false;
				for (int l = 0; l < a.size(); l++) {
					if (a[i] + a[j] + a[k] == a[l]) {ok = true;}
				}
				if (!ok) {cout << "NO\n"; return;}
			}
		}
	}
	cout << "YES\n";
}
int main() {
	int _;
	cin >> _;
	while (_ --) {
		solved();
	}
 
	return 0;
}