Технокубок 2022 - Отборочный Раунд 2 |
---|
Закончено |
Это интерактивная задача.
У жюри была тождественная перестановка $$$a$$$ длины $$$n$$$ ($$$a_i = i$$$).
Жюри выбрало три целых числа $$$i$$$, $$$j$$$, $$$k$$$ такие, что $$$1 \leq i < j < k \leq n$$$, $$$j - i > 1$$$. После этого жюри развернуло отрезки $$$[i, j - 1]$$$ и $$$[j, k]$$$ в последовательности $$$a$$$.
Разворачивание подотрезка $$$[l, r]$$$ последовательности $$$a$$$ означает переворот подотрезка элементов $$$a_l, a_{l+1}, \ldots, a_r$$$ в последовательности, то есть $$$a_l$$$ меняется местами с $$$a_r$$$, $$$a_{l+1}$$$ с $$$a_{r-1}$$$, и т. д..
Вам дано число $$$n$$$. Вы должны найти $$$i$$$, $$$j$$$, $$$k$$$ с помощью некоторых запросов.
За один запрос вы можете выбрать два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) и узнать количество инверсий на подотрезке $$$[l, r]$$$ последовательности $$$a$$$. Жюри скажет вам количество пар $$$(i, j)$$$ таких, что $$$l \leq i < j \leq r$$$ и $$$a_i > a_j$$$.
Найдите числа $$$i$$$, $$$j$$$, $$$k$$$, выбранные жюри, сделав не более $$$40$$$ запросов.
Жюри фиксирует числа $$$i$$$, $$$j$$$ и $$$k$$$ до запуска вашей программы и не меняет их в зависимости от ваших запросов.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных. Далее следуют наборы входных данных.
В единственной строке для каждого набора входных данных дано целое число $$$n$$$ ($$$4 \leq n \leq 10^9$$$). После его считывания, вы должны перейти к процессу взаимодействия с программой жюри и делать запросы. После того, как вы дали ответ, вы должны:
Чтобы спросить количество инверсий на отрезке $$$[l, r]$$$, выведите «? l r», где ($$$1 \leq l \leq r \leq n$$$). Вы можете сделать не более $$$40$$$ таких запросов в каждом тестовом случае. В ответ вы получите целое число $$$x$$$.
Чтобы дать ответ, выведите «! i j k», где $$$i$$$, $$$j$$$, $$$k$$$ — числа, которые, как вы считаете, загадало жюри. После этого вы должны перейти к следующему набору или завершить программу.
После вывода запроса или ответа не забудьте вывести перевод строки и сбросить буфер выходного потока. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
Взломы
Чтобы сделать взлом, используйте следующий формат:
Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных.
Каждая из следующих $$$t$$$ строк содержит четыре целых числа $$$n$$$, $$$i$$$, $$$j$$$, $$$k$$$ ($$$4 \leq n \leq 10^9$$$, $$$1 \leq i < j < k \leq n$$$, $$$j - i > 1$$$).
2 5 4 3 3 5 2 2 1
? 1 5 ? 2 5 ? 3 5 ! 1 3 5 ? 1 5 ? 2 5 ? 3 5 ! 2 4 5
В первом наборе входных данных $$$i = 1$$$, $$$j = 3$$$, $$$k = 5$$$, поэтому последовательность $$$a$$$ равна $$$[2, 1, 5, 4, 3]$$$.
Во втором наборе входных данных $$$i = 2$$$, $$$j = 4$$$, $$$k = 5$$$, поэтому последовательность $$$a$$$ равна $$$[1, 3, 2, 5, 4]$$$.
Название |
---|