Шардирование постов
Contest: VK Cup 2019 - Квалификация (Engine)
Tags: *special, binary search, interactive

Это интерактивная задача.

Когда данных становится слишком много и они не помещаются на один сервер, их приходится шардировать. Рассмотрим систему хранения постов пользователей, которая расположена на $$$S$$$ серверах, нумеруемых с единицы. Каждый раз когда пользователь пишет пост, ему выдается уникальный идентификатор в пределах от 1 до $$$10^{18}$$$ и сохраняется на случайный сервер. Чем позже был создан пост, тем больше его $$$id$$$. Иногда посты удаляются, поэтому на серверах может лежать существенно разное количество постов.

Рассмотрим все неудаленные $$$id$$$ постов пользователя и отсортируем их по возрастанию. Вам хочется узнать $$$k$$$-й из них. Для этого вы можете послать не более 100 дополнительных запросов. Каждый запрос имеет формат «? $$$i$$$ $$$j$$$». В ответ вы получите идентификатор $$$j$$$-го по возрастанию поста пользователя среди хранящихся на $$$i$$$-м сервере. Когда вы считаете, что знаете $$$k$$$-й по возрастанию идентификатор, вместо запроса необходимо вывести ответ в формате «! $$$id$$$».

Interaction format:
В первой строке записано два числа $$$n$$$ и $$$S$$$ ($$$1 \le n \le 100, 1 \le S \le 5$$$) — количество пользователей для которых необходимо независимо решить задачу, а также количество серверов, на которых хранятся посты.

Далее необходимо $$$n$$$ раз решить задачу. Вначале необходимо считать $$$S$$$ чисел $$$a_1, a_2, ... a_S$$$ ($$$0 \le a_i; \sum a_i \le 10^5$$$) — количество постов пользователя на каждом сервере. В следующей строке будет задано число $$$k$$$ ($$$1 \le k \le \sum a_i $$$) — идентификатор какого по возрастанию поста необходимо узнать.

Далее необходимо совершить не более 100 запросов в формате, который описан в условии.

Заметим, что ограничение на количество запросов действует на каждого пользователя отдельно, поэтому при переходе к следующему тесту счетчик вопросов сбрасывается.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
В примере на первом сервере хранятся посты с $$$id$$$ 1, 3 и 10. А на втором 5 и 7. Необходимо найти третье по возрастанию число, это 5.

Example input:
1 2
3 2
3

3

5

10

Example output:
? 1 2

? 2 1

? 1 3

! 5

Editorial:
Для каждого сервера будем поддерживать отрезок постов, среди которых, возможно, есть $$$k$$$-й. Изначально в этот отрезок будут попадать все посты. Для каждого отрезка возьмём средний пост в нем и узнаем его $$$id$$$.
Рассмотрим отрезок, у которого $$$id$$$ среднего поста самый маленький (пусть он равен $$$X$$$). Тогда всего существует не более $$$\sum \frac{len_i}{2}$$$ постов с $$$id$$$ не больше $$$X$$$. Если $$$k$$$ больше $$$\sum \frac{len_i}{2}$$$, то можно с уверенностью сказать, что первая половина отрезка, у которого самый маленький средний $$$id$$$ поста, нам не интересна. Тогда можно уменьшить этот отрезок в два раза и рекурсивно продолжить решать задачу.
Аналогично в некоторых случаях можно убрать верхнюю половину отрезка с самым большим средним $$$id$$$.
Можно показать, что всегда получится воспользоваться либо первой опцией, либо второй. А значит, каждый раз один из отрезков уменьшится в два раза. А после этого необходимо будет сделать один дополнительный запрос, чтобы узнать $$$id$$$ среднего поста в новом отрезке.
Таким образом за $$$S \log(len)$$$ запросов можно узнать $$$k$$$-й пост.