Это интерактивная задача.
Вернувшись после отдыха на Золотом побережье Австралии, Пенчик забыл привезти домой подарки для своей домашней утки Дуонг Кан! Но, возможно, прекрасная задача, созданная в глубоких раздумьях на живописных пляжах, станет идеальным сувениром.
Существует скрытая перестановка\(^{\text{∗}}\) \(p\) длины \(n\), где \(n\) — четное. Вам разрешается задавать следующие вопросы:
- Выбрать подпоследовательность\(^{\text{†}}\) перестановки \(p\) с четной длиной \(4\le k\le n\). Интерактор вернет значения двух медиан\(^{\text{‡}}\) в выбранной подпоследовательности.
Найдите индексы двух медиан в перестановке \(p\), используя не более \(80\) запросов.
Обратите внимание, что интерактор является неадаптивным. Это означает, что перестановка \(p\) фиксирована изначально и не будет меняться в зависимости от ваших запросов.
Протокол взаимодействия
Чтобы сделать запрос, выведите одну строку в следующем формате:
- \(\mathtt{?}\;k\;x_1\;x_2 \ldots x_{k-1}\;x_k\) (\(4\le k\le n\), \(k\) — четное, \(1 \le x_i \le n\), \(x_i\) — попарно различные) — длина выбранной подпоследовательности, затем индексы выбранной подпоследовательности.
После каждого запроса вы должны прочитать строку, содержащую два целых числа \(m_1\) и \(m_2\) (\(1 \le m_1 < m_2 \le n\)) — значения двух медиан в массиве \([p_{x_1}, p_{x_2}, \ldots, p_{x_{k-1}}, p_{x_k}]\).
Вы можете сделать не более \(80\) таких запросов в каждом наборе входных данных.
Чтобы дать окончательный ответ, выведите одну строку в следующем формате:
- \(\mathtt{!}\;i_1\;i_2\) (\(1\le i_1, i_2 \le n\)) — индексы двух медиан.
Обратите внимание, что порядок вывода \(i_1\) и \(i_2\) не имеет значения. Другими словами, ваше решение будет верным, если \(p_{i_1} = \frac{n}{2}\) и \(p_{i_2} = \frac{n}{2} + 1\), или \(p_{i_1} = \frac{n}{2} + 1\) и \(p_{i_2} = \frac{n}{2}\).
После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода\(^{\text{∗}}\). В противном случае вы получите вердикт Решение «зависло».
На любом шаге взаимодействия, если вы считали \(-1\) вместо корректных данных, ваше решение должно немедленно завершиться. Это означает, что ваше решение получит вердикт Неправильный ответ из-за некорректного запроса или любой другой ошибки. Если программа не завершится, вы можете получить любой вердикт, так как ваша программа продолжит чтение из закрытого потока.
Формат взломов
Для взломов используйте следующий формат.
Первая строка должна содержать \(t\) — количество наборов входных данных.
Первая строка каждого набора входных данных должна содержать одно целое число \(n\).
Вторая строка каждого набора входных данных должна содержать перестановку \(p_1, p_2, \ldots, p_n\) длины \(n\).
В качестве примера формата взлома приведём тест из примера:
2
6
6 2 3 5 1 4
10
10 9 8 7 6 5 4 3 2 1
Примечание
В первом наборе входных данных скрытая перестановка равна \(p = [6, 2, 3, 5, 1, 4]\).
- В первом запросе была выбрана вся перестановка. Две медианы всей перестановки \(p\) равны \(3\) и \(4\).
- Индексы выбранной подпоследовательности во втором запросе — \(3\), \(6\), \(1\) и \(5\). Интерактор возвращает две медианы подпоследовательности \([p_3, p_6, p_1, p_5] = [3, 4, 6, 1]\), которые равны \(3\) и \(4\).
- Индексы выбранной подпоследовательности во втором запросе равны \(3\), \(6\), \(2\) и \(5\). Интерактор возвращает две медианы подпоследовательности \([p_3, p_6, p_2, p_5] = [3, 4, 2, 1]\), которые равны \(2\) и \(3\).
Ответ «! 3 6» верен, так как \(p_3 = 3\) и \(p_6 = 4\).
Во втором наборе входных данных скрытая перестановка равна \(p = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]\).
- Индексы выбранной подпоследовательности во втором запросе — \(1\), \(3\), \(7\), \(8\), \(9\) и \(10\). Интерактор возвращает две медианы подпоследовательности \([p_1, p_3, p_7, p_8, p_9, p_{10}] = [10, 8, 4, 3, 2, 1]\), которые равны \(3\) и \(4\).
- Индексы выбранной подпоследовательности во втором запросе равны \(1\), \(2\), \(3\), \(4\), \(5\), \(6\), \(7\) и \(8\). Интерактор возвращает две медианы подпоследовательности \([p_1, p_2, p_3, p_4, p_5, p_6, p_7, p_8] = [10, 9, 8, 7, 6, 5, 4, 3]\), которые равны \(6\) и \(7\).
Ответ «! 5 6» верен, так как \(p_5 = 6\) и \(p_6 = 5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
6
3 4
3 4
2 3
10
3 4
6 7
|
? 6 1 2 3 4 5 6
? 4 3 6 1 5
? 4 3 6 2 5
! 3 6
? 6 1 3 7 8 9 10
? 8 1 2 3 4 5 6 7 8
! 6 5
|