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

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

ru en cn

5929940

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

Иванов Александр

Время

08:55<< 24.12.2021 08:56 (20 д. 08:56)

Обработка

08:56 ... 08:56 (4.80 сек.)

Файл

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

Турнир

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

Задача

B: Binary/linear search

Набор тестов

Ограничения

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

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

Принято

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

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

≡

#pragma once

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <list>

template<typename T, typename Iterator>
Iterator FindImpl(const T& value,
                    Iterator first,
                    Iterator last,
                    std::random_access_iterator_tag) {
    int l = 0, r = last - first - 1;
    while (l < r) {
        int m = l + (r - l) / 2;
        if (*(first + m) < value) {
            l = m + 1;
        } else {
            r = m;
        }
    }
    if (first + l < last && *(first + l) == value) {
        return first + l;
    }
    return last;
}

template<typename T, typename Iterator>
Iterator FindImpl(const T& value,
                    Iterator first,
                    Iterator last,
                    std::bidirectional_iterator_tag) {
    Iterator it = first;
    T v = value;
    while (it != last && *it < v)
        it++;
    if (it != last && *it == value) {
        return it;
    }
    return last;
}

template<typename T, typename Iterator>
Iterator Find(const T& value, Iterator first, Iterator last) {
    typedef typename std::iterator_traits<Iterator>::iterator_category category;
    return FindImpl(value, first, last, category());
}

(1 462 b)

0.132s 0.008s 9