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 <crazy.logic.k...@gmail.com> 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 <saurab...@gmail.com>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 algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
