eolymp
Competitions

2021-2022 ICPC, SEERC, 1/8 Final

Медіанне божевілля

\textit{Це інтерактивна задача.} Загадана деяка перестановка $p$ чисел від $1$ до $n$, де $n$ \textbf{парне}. Ви можете задавати запити наступного вигляду: \begin{itemize} \item Для даного набору різних індексів непарної довжини $a_1, a_2, \dots, a_l$, ви можете дізнатись таке число $x$, що $p_x$ є медіаною елементів $p_{a_1}, p_{a_2}, \dots, p_{a_l}$. \end{itemize} \textbf{Відомо, що $p_1<p_n$}. Вгадайте перестановку $p$ за \textbf{не більше ніж $\frac{3n}{2}$} запитів. Гарантується, що перестановка зафіксована перед початком взаємодії. Іншими словами, \textbf{інтерактор не адаптивний}. Нагадаємо, що медіана непарної кількості чисел визначається наступним чином: Нехай $b_1, b_2, \ldots, b_{2k+1}$ --- це ці числа в порядку зростання (де $2k+1$ --- кількість чисел). Тоді медіаною є число $b_{k+1}$. \Interaction Почніть взаємодію, зчитавши одне ціле число $n$ ($2 \le n \le 1000$, $n$ парне) --- довжину перестановки. Щоб задати питання, необхідно вивести в одному рядку спочатку символ <<\t{?}>>, потім ціле число $l$, а потім $l$ цілих чисел $a_i$ ($1 \le l \le n$, $1 \le a_i \le n$, $l$ непарне, всі $a_i$ попарно різні)~--- індекси, для яких необхідно знайти медіану. У відповідь програма журі виведе таке число $x$, що $p_x$ є медіаною елементів $p_{a_1}, p_{a_2}, \dots, p_{a_l}$. Коли ви визначили перестановку, то виведіть спочатку символ <<\t{!}>>, а потім $n$ чисел $p_1, p_2, \ldots, p_n$. Після цього ваша програма має завершити роботу. Після кожного запиту і виводу відповіді не забудьте вивести перехід рядка і скинути буфер виводу. Для скидання буферу використовуйте: \begin{itemize} \item \texttt{fflush(stdout)} чи \texttt{cout.flush()} в C++; \item \texttt{System.out.flush()} в Java; \item \texttt{flush(output)} в Pascal; \item \texttt{stdout.flush()} в Python; \end{itemize} \Note В прикладі загадана перестановка $p = $$(1, 3, 2, 4)$. Перший запит в прикладі --- хочемо дізнатись медіану елементів $p_2, p_3, p_4$, що дорівнюють $3, 2, 4$ відповідно. Медіана цих чисел --- $3$, тобто $p_2$, тому інтерактор відповідає числом $2$. Другий запит в прикладі --- хочемо дізнатись медіану елементів $p_1, p_3, p_4$, що дорівнюють $1, 2, 4$ відповідно. Медіана цих чисел --- $2$, тобто $p_3$, тому інтерактор відповідає числом $3$. Третій запит в прикладі --- хочемо дізнатись медіану елементів $p_1, p_2, p_4$, що дорівнюють $1, 3, 4$ відповідно. Медіана цих чисел --- $3$, тобто $p_2$, тому інтерактор відповідає числом $2$. Четвертий запит в прикладі --- хочемо дізнатись медіану елементів $p_1, p_2, p_3$, що дорівнюють $1, 3, 2$ відповідно. Медіана цих чисел --- $2$, тобто $p_3$, тому інтерактор відповідає числом $3$.
Time limit 3 seconds
Memory limit 256 MiB
Input example #1
4
1 3 2 4
Output example #1
Author Anton Trygub