Ти k-ий?#198

Ти k-ий? (Editorial)

Що саме шукаємо. Позначимо через c_1, c_2, c_3 кількості елементів, узятих із початків масивів. Тоді -й елемент об'єднання дорівнює

\min_{c_1+c_2+c_3 = k} \ \max\bigl(a[c_1],\, b[c_2],\, c[c_3]\bigr),

де a[0] = -\infty. Отже треба знайти оптимальний «розріз», а не сам масив.

Два правила обміну. Триматимемо для кожного масиву відрізок [L_t, R_t], у якому напевно лежить оптимальне c_t. Візьмемо будь-які m_t \in [L_t, R_t] і запитаємо значення a_t[m_t]. Далі:

  • якщо \sum m_t \ge k, то серед перших m_t елементів уже назбиралось чисел, і всі вони не перевищують V = \max_t a_t[m_t]; отже відповідь , і для масиву , на якому цей максимум досягається, існує оптимум із c_Y \le m_Y. Опускаємо R_Y = m_Y;

  • якщо \sum m_t < k, то навпаки: для масиву з найменшим a_X[m_X] існує оптимум із c_X \ge m_X. Піднімаємо L_X = m_X.

Обидва твердження доводяться однаково — обміном: переносимо одиницю з «дорогого» масиву в «дешевий» і перевіряємо, що максимум не зростає.

Чому запитів мало. Правила дозволяють будь-які m_t всередині відрізків, тож беремо середини. Кожен крок скорочує вдвічі один відрізок, а решта масивів залишаються з тими самими серединами — їхні значення вже в кеші. Тому крок коштує один новий запит, а кроків усього \sum_t \log_2 |t| \approx 3\log_2 10^6 = 60.

Дрібниця, на якій легко застрягти: при округленні вниз завжди прогресує лише перше правило, при округленні вгору — лише друге. Тому спершу пробуємо «підлоги» (якщо сума ), потім «стелі» (якщо сума ), а в рідкісному проміжному випадку добираємо решту до рівно , віддаючи надлишок найширшому відрізку. Наприкінці, коли всі відрізки стиснуті до кількох варіантів, перебираємо їх напряму й беремо мінімум максимумів.

Технічно. Обов'язково кешуйте відповіді: повторний запит — це змарнована квота. Не забувайте fflush після кожного рядка й негайно завершуйте роботу, отримавши . Разом виходить близько запитів навіть на найбільших тестах, що вкладається в найсуворіше обмеження Q = 65.