@keyan..your advice was really very helpful...the time limit has come under
control ...1.4s but now i am getting WA though my code is giving right ans
for the test cases...can you plz help me in figuring out where it fails ..
On Sun, Jun 12, 2011 at 12:59 AM, keyan karthi <keyankarthi1...@gmail.com>wrote:
>
> hint: u ve commented some vital part of ur code ;)
>
> On Sun, Jun 12, 2011 at 12:46 PM, saurabh singh <saurab...@gmail.com>wrote:
>
>>
>> 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 <keyankarthi1...@gmail.com
>> > 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 <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.
>>>
>>
>>
>>
>> --
>> 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 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.
