forgot to attach the code...here is the modified code..
#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);
}
}
}
sort(a2.begin(),a2.end());
vector<int>::iterator itr;
for(itr=a1.begin();itr!=a1.end();itr++)
{
value=*itr;
//ans+=count(a2.begin(),a2.end(),value);
ans+=upper_bound(a2.begin(),a2.end(),value)-lower_bound(a2.begin(),a2.end(),value);
}
printf("%d",ans);
return 0;
}
On Sun, Jun 12, 2011 at 1:07 AM, nicks <[email protected]> wrote:
> @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
> <[email protected]>wrote:
>
>>
>> hint: u ve commented some vital part of ur code ;)
>>
>> On Sun, Jun 12, 2011 at 12:46 PM, saurabh singh <[email protected]>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 <
>>> [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.
>>>
>>
>> --
>> 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.
