ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1196. History Exam

Binary search algorithm, but TLE. Why ??
Posted by Yermakov Alex [ONPU] 28 Apr 2010 21:29
#include <iostream>
long int bin( long int a[], long int k, int low , int high );
long int count = 0;
int main()
    {
           int n,i;
           std:: cin >> n;
           long int *A = new long int[n];
           for( i=0; i<n; ++i ) std::cin >> A[i];

           long int m,j,key;
           std::cin >> m;
           long int *B = new long int[m];
           for ( j=0; j<m; ++j ) std::cin >> B[j];

           for ( j=0; j<m; ++j )
               {      key = B[j];
                      if (bin(A, key, 0, n-1)) ++count;
               }

           std:: cout << count;
           delete [] A;
           delete [] B;
           return 0;
    }
long int bin( long int a[], long int k, int low , int high )
             {
                 int middle;
                 while(low <= high)
                 {
                    middle = low + high;
                    if (k == a[middle]) return a[middle];
                    else if(k < a[middle]) high = middle-1;
                         else low = middle+1;
                 }
             return 0;
             }
Re: Binary search algorithm, but TLE. Why ??
Posted by Baurzhan 29 Apr 2010 17:15
Don't use cin/cout in the case of big input/output. Use scanf("%I64d",&x)/printf("%I64d",x);

Edited by author 29.04.2010 17:15
Re: Binary search algorithm, but TLE. Why ??
Posted by dAFTc0d3r [Yaroslavl SU] 29 Apr 2010 22:26
middle = low + high; ????
Re: Binary search algorithm, but TLE. Why ??
Posted by Yermakov Alex <ONPU> 29 Apr 2010 23:48

Edited by author 29.04.2010 23:57

Edited by author 29.04.2010 23:58
Re: Binary search algorithm, but TLE. Why ??
Posted by Yermakov Alex <ONPU> 29 Apr 2010 23:51
I changed it...thank's.
middle = (low + high)/2
there's no TLE . 0.562



Edited by author 30.04.2010 00:10
Re: Binary search algorithm, but TLE. Why ??
Posted by dAFTc0d3r [Yaroslavl SU] 1 May 2010 17:43
Nice. :)