I got TLE
![:cry:](./images/smilies/icon_cry.gif)
Please help!
Moderator: Board moderators
Code: Select all
#include <stdio.h>
int main ( void )
{
long sequence[1010] , input ;
int NumOfElement , i , j , k , l ;
char flag ;
/* freopen ( "10125.in" , "r" , stdin ) ;
freopen ( "10125.out" , "w" , stdout ) ;*/
while ( 1 )
{
scanf ( "%i" , &NumOfElement ) ;
if ( !NumOfElement ) break ;
for ( i = 0 ; i < NumOfElement ; i ++ )
{
scanf ( "%li" , &input ) ;
for ( j = 0 ; j < i && sequence[j] <= input ; j ++ ) ;
for ( k = i - 1 ; k >= j ; k -- )
sequence[k+1] = sequence[k] ;
sequence[j] = input ;
}
for ( i = NumOfElement - 1 , flag = 0 ; i > 2 ; i -- )
{
for ( j = i - 1 ; j > 1 ; j -- )
{
for ( k = j - 1 ; k > 0 ; k -- )
{
for ( l = k - 1 ; l >= 0 ; l -- )
if ( sequence[i] == sequence[j] + sequence[k] + sequence[l] ) { flag = 1 ; break ; }
if ( flag ) break ;
}
if ( flag ) break ;
}
if ( flag ) break ;
}
if ( flag )
printf ( "%li\n" , sequence[i] ) ;
else printf ( "no solution\n" ) ;
}
return 0 ;
}
Whinii F. wrote:Just got AC.But my program runs about 1.8sec..
![]()
There are much faster solutions. Is there a better algorithm?
Can anybody got below 0.5sec, answer my question?
Code: Select all
#include<stdio.h>
#include<stdlib.h>
typedef int LONG;
#define INF 2000000000
LONG arr[1005],data[1000009];
int index;
int sfunc1(void const *a,void const *b)
{
LONG p,q;
p=*(LONG *)a;
q=*(LONG *)b;
if(p>q) return 1;
else return -1;
return 0;
}
int binsearch(LONG x)
{
int low,high,mid;
low=0;
high=index;
while(low<(high-1))
{
mid=(low+high)/2;
if(x<data[mid]) high=mid;
else low=mid;
}
if(x==data[low]) return low;
return -1;
}
void main()
{
int i,j,N,flag,r;
LONG a,max;
//freopen("10125.in","r",stdin);
while(scanf("%d",&N)==1 && N)
{
for(i=0;i<N;i++) scanf("%d",&arr[i]);
qsort(arr,N,sizeof(arr[0]),sfunc1);
index=0;
for(i=0;i<N;i++)
{
for(j=i+1;j<N;j++)
{
data[index++]=arr[i]+arr[j];
}
}
qsort(data,index,sizeof(data[0]),sfunc1);
max=-INF;
flag=1;
for(i=N-1;i>=0;i--)
{
for(j=i-1;j>=0;j--)
{
a=(arr[i]-arr[j]);
r=binsearch(a);
if(r!=-1)
{
if(arr[i]>max) max=arr[i];
flag=0;
}
a=(data[j]-arr[i]);
r=binsearch(a);
if(r!=-1)
{
if(arr[j]>max)max=arr[j];
flag=0;
}
}
}
if(flag==1) printf("no solution\n");
else printf("%d\n",max);
}
}
Read problem description more carefully:rasel04 wrote:Procedure:
1. Get all a+b and sorting them.
2.Find all (d-c) and find this by binary search from the above array.
But why wrong answer. PLS help.
And come back when you get TLE.where a, b, c, and d are distinct elements of S.
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#define MAX 1000
int a, b, c, d, n, arre[MAX + 1];
int pepe(const void *a, const void *b)
{
return *((int*)a) - *((int*)b);
}
void ReadData()
{
for (a = 0; a < n; a++)
scanf("%d", &arre[a]);
}
void MakeSolu()
{
qsort(arre, n, sizeof(int), pepe);
for (d = n - 1; d >= 3; d--)
for (c = d - 1; c >= 2; c--)
for (b = c - 1; b >= 1; b--)
for (a = b - 1; a >= 0; a--)
if (arre[a] + arre[b] + arre[c] == arre[d])
{
printf("%d\n", arre[d]);
return;
}
puts("no solution");
}
int main()
{
scanf("%d", &n);
while (n)
{
ReadData();
MakeSolu();
scanf("%d", &n);
}
return 0;
}
Code: Select all
5
-8 4 10 11 14