2 курс. Программирование на C++. Турнир 3, осень 2021

вход курсы / турниры задачи участники консоль модули компиляторы ключевые слова результаты

ru en cn

5889720

Пользователь

Хомулло Степан Николаевич

Время

01:05<< 10.12.2021 01:06 (6 д. 01:07)

Обработка

01:06 ... 01:06 (4,10 сек.)

Файл

5889720.cpp (CLang++ 5.0.0 + Address Sanitizer)

Турнир

2 курс. Программирование на C++. Турнир 3, осень 2021

Задача

B: Binary/linear search

Набор тестов

Ограничения

Время: 1с Память: 4000Мб

Состояние [?]

Принято

код | результаты

[печатать | | ]

≡

template<class T, class It>
auto FindImplemented(T value, It begin_it,
                     It end_it, std::random_access_iterator_tag) {
    auto begin = begin_it;
    auto end = end_it;
    size_t size = std::distance(begin, end);
    auto middle_it = begin + size / 2;

do {
        if (size == 2) {
            if (*middle_it == value)
                return middle_it;
            else
                end = middle_it;
        } else {
            if (value < *middle_it)
                end = middle_it + 1;
            else
                begin = middle_it;
        }

size = std::distance(begin, end);
        middle_it = begin + size / 2;
    } while (size > 1);

if (*middle_it == value)
        return middle_it;

return end_it;
}

template<class T, class It, class IteratorTag>
auto FindImplemented(T value, It begin_it, It end_it, IteratorTag) {
    auto it = begin_it;

while (it != end_it) {
        if (*it == value)
            return it;

it++;
    }

return it;
}

template<class T, class It>
auto Find(T value, It begin_it, It end_it) {
    typedef typename std::iterator_traits<It>::iterator_category category;
    return FindImplemented(value, begin_it, end_it, category());
}

(1 286 b)

0.095s 0.032s 9