Simple 思考题

Ninja

Try to find any of three integers X,Y,Z in a given integer array A of length N so that X+Y=Z.

Example

Input:
A={1,2,3}
Output:
X=1,Y=2,Z=3
Input:
A={0}
Output:
X=0,Y=0,Z=0
Input:
A={1,9,2,6,0,8,1,7}
Output:
X=1,Y=8,Z=9
Input:
A={1,2,4}
Output:
NO

Constraints

Subtask 1(10%):N<=1000
Subtask 2(30%):N<=20000,Ai<=20000
Subtask 3(30%):N<=1e5,Ai<=1e5
Subtask 4(30%):N<=1e5,Ai<=1e9

Solution

For Subtask 2, we can maintain a Bitmask x and y. the i-th bit of x is true if i is in the array. let y=x.clone()
Then we sort the array, for each number i, x<<=(a[i]-a[i-1]). If x&y!=0 then we find the answer
Time Complexity is O(n^2/w)