Всем привет! Придумал другое решение на задачу F2, но почему-то не хочет заходить.
Я для каждого отрезка 1..8, 9..16, 17..23 и т. д. узнаю сразу на них сумму. Далее строю ДО на сумму по заданным значениям, где делаю спуск в ту восьмёрку, которая подходит текущему запросу (i-й ноль). Далее делаю обычный бин поиск. Затем обновляю в данной восьмёрке значение на +1. По идее количество операций равно n / 8 + 3 * t = 55000, что подходит под ограничения. Кто-нибудь может объяснить, почему это не работает, или где я что-то делаю неправильно?
Код: 115451217.
Бинарный поиск имеет сложность O(log n). Но это вовсе не значит, что он сделает столько операций. Он может сделать log n + 1, log n + 2 операций. Например: 01111111. Алгоритм сначала пойдет в i = 4, затем i = 2; i = 1; i = 0. Итого — 4 операции (не 3). У меня в решении подобная идея, но нет бинпоиска: 115410248
Понял, спасибо большое!
Просто сделай другой размер блоков. Например, возьми 20.