ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1196. Экзамен по истории

Binary search algorithm, but TLE. Why ??
Послано Yermakov Alex [ONPU] 28 апр 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 ??
Послано Baurzhan 29 апр 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 ??
Послано dAFTc0d3r [Yaroslavl SU] 29 апр 2010 22:26
middle = low + high; ????
Re: Binary search algorithm, but TLE. Why ??
Послано Yermakov Alex <ONPU> 29 апр 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 ??
Послано Yermakov Alex <ONPU> 29 апр 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 ??
Послано dAFTc0d3r [Yaroslavl SU] 1 май 2010 17:43
Nice. :)