Find has an approximately linear time complexity @tushar_harsh. Check this out: http://www.cplusplus.com/reference/algorithm/find/
According to your set, P(x) = (x - 1)(x - 3)(x - 5)(x - 100)(x - 120)
In this case putting your queries in place of x gives the following output which is expected from the problem:
NEGATIVE
POSITIVE
NEGATIVE
POSITIVE
NEGATIVE
0
which does not match with your either of your expected or codeās output. No idea how your code got AC.
Hey shouldnāt the actual output be :
NEGATIVE
POSITIVE
NEGATIVE
POSITIVE
NEGATIVE
0
I overlooked the negative sign. Yes, the expected output is
NEGATIVE
POSITIVE
NEGATIVE
POSITIVE
NEGATIVE
0
Let me edit that.
āPoor test casesā is the only reason. Author and tester are responsible for that.
oh ! all this time I thought it was constant, my bad not considering it, thanks !!
Your code does not even pass the example test case. Please refer to the proper usage of lower_bound algorithm function. Your code got AC due to their poor test cases.
You are sorting the array Q timesā¦just sort it once before taking the queries
I have no idea what is the time complexity is. and I canāt see any constraint issue in the product variable.
Such a silly mistake I madeā¦Thanks
Can somebody please explain why I am getting TLE here, I just tried a simple brute force approach. It would be kind if you also explain the complexities here, I didnāt understand the concept,
Link: Here is the solution: https://www.codechef.com/viewsolution/48416750
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
std::ios_base::sync_with_stdio(0);
cin.tie(0);
int n,q;
cin >> n >> q;
int a[n];
for(int i=0;i<n;i++){
cin >> a[i];
}
int cnt,x,l;
while(qā){
cnt=0;
l=0;
cin >> x;
for(int i=0;i<n;i++){
int k = (x-a[i]);
if(x==a[i]){
l=1;
break;
}
else if(k<0){
cnt++;
}
}
if(l==1){
cout <<0<<endl;
}
else if(cnt%2 == 0)
cout <<āPOSITIVEā<<endl;
else
cout <<āNEGATIVEā<<endl;
}
return 0;
}
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/*Finds the first occurence of number greater than a using binary search and returns
(n-(index of the digit)) which is the number of values greater than a.
If a number is equal to a it returns -1*/
int bin(vector<int> v,int a,int n)
{
int str=0,en=n-1,pos=0;
while(str<=en){
int mid=((str+en)/2);
if(v[mid]>a){
pos=mid;
en=mid-1;
}
else if(v[mid]==a){
return -1;
}
else{
str=mid+1;
}
}
return (n-pos);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
unsigned long long n,j,k;
cin>>n>>k;
vector<int> v;
for(int i=0;i<n;i++){
cin>>j;
v.push_back(j);
}
sort(v.begin(),v.end());
while(k--){
int a;
cin>>a;
//If the number of values greater than a is even then it returns positive
cout<<(((bin(v,a,n)&1)==0)?"POSITIVE":((bin(v,a,n)==-1)?"0":"NEGATIVE"))<<endl;
}
}
Can someone tell me where i went wrong. It would help me a lot. Thank you.
bin
should take v
by reference instead of by value, to avoid TLE.
Yes. It is working now. Why does this work though??.
If you pass by value, you make a copy of v
every time you call bin
.
Ohh okay. Thanks a lot.
// help in debugging my code as it gives correct output on running customs //input but canāt submit successfully.
include
#include<bits/stdc++.h>
#include<bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int n,q;cin>>n>>q;
vectora;
for(int i=0; i<n;i++){
int a1;cin>>a1;
a.push_back(a1);
}
sort(a.begin(),a.end());
vector::iterator it;
while(q--){
int x;cin>>x;
if(binary_search(a.begin(),a.end(),x))cout<<"0";
else{
if(x<a[0]||(n%2==0&&x>a[n-1]))cout<<"POSITIVE"<<endl;
else if(x>a[n-1]&&n%2!=0){
cout<<"NEGATIVE"<<endl;
}
else {
it = upper_bound(a.begin(),a.end(), x);
int it2 = it - a.begin();
if(it2%2==0)cout<<"POSITIVE\n";
else cout<<"NEGATIVE"<<endl;
}
}
}
return 0;
}