Wave Solution TLE altough for a similar sol time is 0.08 sec

Link to que
https://www.codechef.com/COOK130B/problems/WAV2
Link to submission
https://www.codechef.com/COOK130B/status/WAV2,s1g1r
NOTE(in my above solutions i have used endl but even after trying \n it doesnt make much difference. )
The below code is for the que wave which gets solved in 0.08 seconds but the one below it is almost similar code to it(only difference is i have solved it through a function)but gets TLE. I am new to CP,can anyone help me understand why its happening.
Code 1 TL 0.08 sec
link to code 1https://www.codechef.com/viewsolution/48230408
Link to code 2 TLE
https://www.codechef.com/viewsolution/48230751
Link to code 3 TLE(almost similar to sol 1)
https://www.codechef.com/viewsolution/48230828

Code 1 TL 0.08 sec

``````#include<bits/stdc++.h>
using namespace std;

void solve(){
int n,q;
cin>>n>>q;
vector arr;
for(int i=0;i<n;i++){
int k;
cin>>k;
arr.push_back(k);
}
sort(arr.begin(),arr.end());
for(int i=0;i<q;i++){
int d;
cin>>d;
auto it = lower_bound(arr.begin(), arr.end(), d);
int k = it - arr.begin();
if(k==arr.size()){
cout<<â€śPOSITIVEâ€ť<<"\n";
}
else if (arr[k] == d) {
cout << â€ś0â€ť << â€ś\nâ€ť;
}
else if(k%2==0){
cout<<â€śPOSITIVEâ€ť<<"\n";
}
else {
cout << â€śNEGATIVEâ€ť <<"\n";
}
}
}
int main(){

#ifndef ONLINE_JUDGE
freopen(â€śinput.txtâ€ť,â€śrâ€ť,stdin);
freopen(â€śoutput.txtâ€ť,â€śwâ€ť,stdout);
freopen(â€śerror.txtâ€ť,â€śwâ€ť,stderr);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
``````

Code 2 TLE

``````#include<bits/stdc++.h>
using namespace std;

string find(vector arr,int d){
if(d<arr[0])
return â€śPOSITIVEâ€ť;
else if(d>arr[arr.size()-1])
return â€śPOSITIVEâ€ť;
auto it= lower_bound(arr.begin(), arr.end(), d);
int k=it-arr.begin();
if(arr[k]==d)
return â€ś0â€ť;
if(k%2==0)
return â€śPOSITIVEâ€ť;
else
return â€śNEGATIVEâ€ť;
}

void solve(){
int n,q;
cin>>n>>q;
vector arr;
for(int i=0;i<n;i++){
int k;
cin>>k;
arr.push_back(k);
}
sort(arr.begin(),arr.end());
for(int i=0;i<q;i++){
int d;
cin>>d;
string s=find(arr,d);
cout<<s<<"\n";
}
}
int main(){

#ifndef ONLINE_JUDGE
freopen(â€śinput.txtâ€ť,â€śrâ€ť,stdin);
freopen(â€śoutput.txtâ€ť,â€śwâ€ť,stdout);
freopen(â€śerror.txtâ€ť,â€śwâ€ť,stderr);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
``````
2 Likes

Please either format your code or (better!) link to your submission - the forum software has mangled it and it wonâ€™t compile!

Edit:

While Iâ€™m waiting for this, check that your `find` function takes `arr` by reference instead of by value.

This is O(n) because it makes a copy of your string.
In the first solution, they use lower_bound which is binary search O(logn)

1 Like

same problem bro
due to this problem sometimes i feel like i shouldnâ€™t solve questions on codechef
if anybody can really provide some insights it would be very helpful

Done. Thanks for the link.

Not really The updated code you posted is still completely mangled.

Can u submit this code of Hidden cell problem from lunchtime, when I m submitting itâ€™s showing internal error.
Link :- CodeChef: Practical coding for everyone

I have added the links. If it doesnt work this time too then i am sorry.

1 Like

I have done a solution where i print it without coping the string (code 3 link) but even that gives TLE.

Thanks, they work - see the Edit in my first post (turns out that you are indeed taking `arr` by value - youâ€™ll need to take it by reference instead)

1 Like

Thank You for your help. Now it is running on time. I didnt know calling it without â€ś&â€ť will make it call by value.

1 Like