I did used the library functions but I am getting sigsegv after 0.03 s.I cant understand why?I am presuming sumthing wrong about the implemenatation of bsearch? I am assuming bsearch is returning a pointer to the first found element. On Sun, Jun 12, 2011 at 12:41 PM, keyan karthi <[email protected]>wrote:
> upper_bound and lower_bound does a binary search to get count of alike > terms.. which u tend to sum of to get the ans.. > out of the two arrays, u need to sort one array.. this will be teh vector > in which u do the binary search wit every element of un sorted array.. > this is the approach i used... :) hope this helps... > > the above functions defined in "algorithm" > > > On Sun, Jun 12, 2011 at 12:34 PM, nicks <[email protected]>wrote: > >> and here is my code I'm Getting TLE.... i tried to implement binary search >> but failed bcoz how will i be able to trace the value from one vector into >> another vector if there are any multiple occureneces of any value(i mean i >> have count them).....in this code i i have used count of algorithm which may >> be expensive...suggest a better way plz...thnx in advance !! >> >> >> >> #include<vector> >> #include<iostream> >> #include<algorithm> >> #include<cstdio> >> #include<cmath> >> using namespace std; >> int main() >> { >> int num,ans=0,value,i,j,k,t,a,b,c,d,e,f; >> scanf("%d",&num); >> vector<int> val,a1,a2; >> for(i=0;i<num;i++) >> { >> scanf("%d",&t); >> val.push_back(t); >> } >> for(i=0;i<num;i++) >> { >> a=val[i]; >> for(j=0;j<num;j++) >> { >> b=val[j]; >> for(k=0;k<num;k++) >> { >> c=val[k]; >> t=a*b+c; >> a1.push_back(t); >> } >> } >> } >> for(i=0;i<num;i++) >> { >> d=val[i]; >> for(j=0;j<num;j++) >> { >> e=val[j]; >> for(k=0;k<num;k++) >> { >> f=val[k]; >> t=(f+e)*d; >> a2.push_back(t); >> } >> } >> } >> >> vector<int>::iterator itr; >> for(itr=a1.begin();itr!=a1.end();itr++) >> { >> value=*itr; >> ans+=count(a2.begin(),a2.end(),value); >> } >> >> printf("%d\n",ans); >> return 0; >> } >> >> >> >> >> >> >> On Sat, Jun 11, 2011 at 11:57 PM, saurabh singh <[email protected]>wrote: >> >>> >>> OK here is my code >>> #include<stdio.h> >>> #include<algorithm> >>> #include<utility> >>> using namespace std; >>> int compareints (const void * a, const void * b) >>> { >>> return ( *(long*)a - *(long*)b ); >>> } >>> >>> >>> int main() >>> { >>> int n,s[101],a,b,c,d,e,f; >>> long p1[100009],p2[100009]; >>> int i,j,k; >>> scanf("%d",&n); >>> for(i=0;i<n;i++) scanf("%d",&s[i]); >>> //sort(s,s+i); >>> k=0; >>> for(i=0;i<n;i++) >>> { >>> for(j=0;j<n;j++) >>> { >>> for(int l=0;l<n;l++) >>> { >>> if(s[l]) >>> p1[k++]=(s[i]+s[j])*s[l]; >>> } >>> } >>> } >>> //sort(p1,p1+k); >>> int x=0; >>> for(i=0;i<n;i++) >>> { >>> for(j=0;j<n;j++) >>> { >>> for(int l=0;l<n;l++) >>> { >>> //if(s[l]!=0) >>> p2[x++]=(s[i]*s[j])+s[l]; >>> } >>> } >>> } >>> sort(p2,p2+x); >>> long *pItem; >>> long count=0; >>> for(i=0;i<k;i++) >>> { >>> pItem = (long*) bsearch (&p1[i], p2, x, sizeof (long), >>> compareints); >>> if(pItem){ >>> >>> long *tmp=pItem; >>> if(pItem==p2)while(*(tmp)==p1[i]&&tmp<p2+x){ >>> count++;tmp++;} >>> else >>> if(pItem==(p2+(x-1))) { >>> while(pItem>=p2&&*(pItem)==p1[i]){count++;pItem--;}} >>> else{ >>> tmp++; >>> while(*(tmp)==p1[i]&&tmp<p2+x){ >>> count++;tmp++;} >>> >>> while(pItem>=p2&&*(pItem)==p1[i]){count++;pItem--;} >>> } >>> //count++; >>> } >>> } >>> printf("%ld\n",count); >>> >>> //for(i=0;i<k;i++) printf("%ld ",p1[i]);printf("\n"); >>> //for(i=0;i<x;i++) printf("%ld ",p2[i]);printf("\n"); >>> return 0; >>> } >>> >>> >>> Why is it getting segmentation fault? >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
