160929 recipes

• Задача A. Квадратный корень.

1. unsigned long long -- всё должно быть именно такого типа.

2. unsigned long long l = 0, r = -1; // границы бинпоиска,

3. Чтение до конца файла: добавлен специальный пример по C++

4. У вас WA? Вы тестировали? Спокойно сядьте, и вбейте 20 разных тестов, включая максимальные и минимальные.

5. У вас TL? Может быть, бинпоиск виснет? Может быть, вы не умеете читать файл?

• Задача B. Бинпоиск.

1. Если вы пользуетесь функциями STL lower_bound/upper_bound, в чём может быть проблема? =)

2. TL? Наверное, вы медленно читаете/выводите.

• Задача C. find3.

Если вы вызываете один бинпоиск, а потом линейно проходите по равным, получите TL. Задача решается за O(log n).

• Задача D. minmax.

В этой задаче нужно написать две кучи. Как при удалении из первой кучи быстро найти элемент во второй?

Есть два разных способа, один подход будет на лекции в среду, а второй вы уже знаете с прошлой лекции − "обратные ссылки".

Нужно отдельно хранить массив a[], а в куче хранить не элементы a[i], а индексы i. Кроме того для каждого i нужно помнить pos[i]: heap[pos[i]] = i.