Алдар
ну замени К на N
Алдар
ясно
Алдар
я перепутал задачу
Алдар
я просто бинарный поиск написал)
Vladislav
Давайте в чат про алгоритмы, я расскажу там как писать бинарный поиск, не беспокоясь о corner case'ах и не думая, где надо и не надо прибавлять/вычитать 1
Алдар
а в этой да, много корнер кейсов
Алдар
хотя в этой можно линейно найти границу между монотонными последовательностями
Алдар
хотя не, зачем линейно
Алдар
в общем ищем границу бинарным поиском, а потом число бинарным поиском
Алдар
нужно просто немного порассуждать
Vladislav
граница же дана, ровно посередине массива
Алдар
хехе, точняк
Алдар
тут же 2n элементов
Алдар
тогда вообще просто
Алдар
тогда мы знаем диапазон двух монотонных последовательностей
Алдар
и если К попадает в диапазон, то ищем в этом подмассиве
Dumitru
ой, я ошибся!
Алдар
бинарным поиском
Dumitru
там граница может быть где угоднл
Dumitru
*угодно
Алдар
кек
Алдар
ну давай порассуждаем
Алдар
[left ....mid ....right]
Алдар
нужно взять производную в mid
Алдар
если она положительна, то мид внутри правого подмассива
Алдар
если отрицательна, то внутри левого
Алдар
если имеет разрыв - то мид на границе)
Алдар
как то так
Алдар
еще надо учесть граничные условия
Алдар
находим границу между подмассивами сначала, потом зная диапазоны ищем в подмассивах
Алдар
что скажете?
Алдар
насчет алгоритма, тут только проблема как не сделать сегфолт
Dumitru
насчет алгоритма, тут только проблема как не сделать сегфолт
воооот, я на это чуть не попался
точнее я написал код зная что там будет сегфолт с мыслью исправить через 10 сек, но он сразу меня подрезал
Алдар
короче ставим сразу охранный кейс
Алдар
If(right - left < 3) {...}
Алдар
и внутри вручную перебираем
Алдар
и потом можно смело обращаться к индексам mid - 1, mid, mid + 1
Алдар
лишь бы работало, ну а потом рефакторинг провести
Алдар
если a[mid-1] > a[mid] > a[mid + 1] то мы внутри первого монотонного подмассива
Алдар
если a[mid - 1]> a[mid] < a[mid + 1] то прямо на границе
Алдар
если a[mid -1] < a[mid] < a[mid + 1] то внутри правого монотонного подмассива
Алдар
что скажешь
Крылатый
А миня?
Алдар
а потом дело техники
mattata
Hi, AppleDog!
Светомеч
Ned
@ned_ogl
template <class T>
std::ostream& operator << (std::ostream &out, const Matrix<T> &matrix){
for (size_t i = 0; i < matrix.getRows(); ++i){
for (size_t j = 0; j < matrix.getCols(); ++j)
out << matrix(i, j) << " ";
out << std::endl; // FIXME
}
return out;
}
Не надо здесь endl
Надо. Чтобы построчно выводил. Как иначе?
Anonymous
\n
Vladislav
endl flush'ит поток
Vladislav
сбрасывает все внутренние буферы
Vladislav
http://www.cplusplus.com/reference/ostream/basic_ostream/flush/
Ned
так, а кто меня пулреквестами закидал, пока я спал?
🦥Alex Fails
Я не помню, слал ли
Ned
его зовут VERBiSDiablo
Anonymous
Это мой акк
Ned
ну во-первых. почему header governors а не прагма?
Ned
говорят, прагма работает умнее в наши дни
Anonymous
Не думаю что ее все поддерживают
Ned
уж в наш-то век С++17 не все?
Anonymous
Наверняка кто- то нет
Vladislav
Prefer #pragma once; it is supported on all major vendors (gcc/clang/MSVC) and is least prone to typos/user errors. On mobile, using #pragma once is required.
Vladislav
из нашего codestyle
Fox
А почему на мобильных обязательно?
Ned
с прагмой компиляторы ебались в 2004 году. уже давно всё отремонтировано