The Wave Codechef Solution in C++ | AskTheCode

Codechef June Cook-Off 2021 Solution | The Wave (WAV2) Solution in C++ | AskTheCode

---

Problem:

Chef is stuck in the wavey world of polynomials. You are given all N roots of a polynomial P(x)=∏Ni=1(x−ai). The roots are pairwise distinct integers, but they are not given in any particular order.

To help Chef escape, you should answer Q queries (numbered 1 through Q). For each valid i, in the i-th query, you are given an integer xi and you have to determine whether P(xi) is positive, negative or 0.

---

Input:

• The first line of the input contains two space-separated integers N and Q.

• The second line contains N space-separated integers a1,a2,…,aN.

• Q lines follow. For each valid i, the i-th of these lines contains a single integer xi describing the i-th query.

---

Output:

For each query, print a single line containing the string "POSITIVE", "NEGATIVE" or "0" (without quotes) describing the value of the polynomial for the i-th query.

---

Sample Input:

4 6
1 3 5 100
-2
2
4
80
107
5

---

Sample Output:

POSITIVE
NEGATIVE
POSITIVE
NEGATIVE
POSITIVE
0

---

Code:

#include <iostream>
#include <algorithm> 
#include <vector>
using namespace std;
#define ll long long int
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
	ll n,q;
	cin>>n>>q;
	ll arr[n],xq;
	for(int i=0;i<n;i++){
	    cin>>arr[i];
	}
    sort(arr,arr +n);
	ll x;
	for(int i=0;i<q;i++){
	    cin>>x;
	    
	    ll pos = lower_bound(arr,arr+n,x) - arr;
	    
	    if(pos <n && arr[pos]==x){
	        cout<<"0\n";
	    }
	    else if(pos%2==0){
	        cout<<"POSITIVE\n";
	    }
	    else{
	        cout<<"NEGATIVE\n";
	    }
	}
	return 0;
}