my code using unordered_map run in 2.79secs which is a N^2*(time taken by the unordered_map) my code is below…
#include<bits/stdc++.h>
using namespace std;
int a[4001],b[4001],c[4001],d[4001];
inline void inp( int &n )
{
n=0;
int ch=getc(stdin);int sign=1;
while(ch < ‘0’ || ch > ‘9’ ){if(ch==’-’)sign=-1; ch=getc(stdin);}
while(ch >= ‘0’ && ch <= ‘9’ )
n = (n<<3)+(n<<1) + ch-‘0’, ch=getc(stdin);
n=n*sign;
}
int main()
{
int n;
inp(n);
for(int i=0;i<n;i++)
{
inp(a[i]);
inp(b[i]);
inp(c[i]);
inp(d[i]);
}
unordered_map <int,int> sum1;
sum1.reserve(16000000);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
sum1[c[i]+d[j]] ++;
}
}
int result=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
int sum=-(a[i]+b[j]);
if(sum1.find(sum)!=sum1.end())
result+=sum1[sum];
}
}
printf("%d\n",result);
return 0;
}
then i tried to make it run faster by removing map and adding hashing so that i could get the time in order(N^2) code is below…which ran in 2.00 secs
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define size 1000001
int a[4001],b[4001],c[4001],d[4001];
typedef long long int ll;
struct node{
int number;
int count;
struct node* next;
};
struct node** hash;
void init_hash()
{
hash=(struct node**)malloc(sizesizeof(struct node));
int i;
for(i=0;i<=size;i++)
hash[i]=0;
}
inline void inp( int *n )
{
*n=0;
int ch=getc(stdin);int sign=1;
while(ch < ‘0’ || ch > ‘9’ ){if(ch==’-’)sign=-1; ch=getc(stdin);}
while(ch >= ‘0’ && ch <= ‘9’ )
*n = ((*n)<<3)+((*n)<<1) + ch-‘0’, ch=getc(stdin);
(n)=(n)sign;
}
void hash_it(int num)
{
int pos=(num<0?-num:num);
pos=pos%size;
struct node cur=hash[pos];
while(cur)
{
if(cur->number==num)
{
cur->count++;
return;
}
cur=cur->next;
}
struct node head=malloc(sizeof(struct node));
head->count=1;
head->number=num;
head->next=hash[pos];
hash[pos]=head;
}
int get_it(int num)
{
int pos=(num<0?-num:num);
pos=pos%size;
struct node cur=hash[pos];
while(cur)
{
if(cur->number==num)
{
return cur->count;
}
cur=cur->next;
}
return 0;
}
int main()
{
freopen(“program.txt”,“r”,stdin);
int n;
inp(&n);
int i,j,k;
init_hash();
for(i=0;i<n;i++)
{
inp(&a[i]);
inp(&b[i]);
inp(&c[i]);
inp(&d[i]);
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
int sum=a[i]+b[j];
hash_it(sum);
}
}
int count=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
int sum=-(c[i]+d[j]);
if(k=get_it(sum))
{
count+=k;
}
}
}
printf("%d\n",count);
return 0;
}
i cannot make it run faster can anyone plz tell how to make it run faster
i have seen in the ranking of this problem that some people have done it within 1 secs