AT_kupc2020_l.Inside Story of Median Query

这是一个带有交互元素的问题。

Alice 有一个由从 $1$ 到 $N$ 组成的整数排列。Alice 的朋友 Bob 不喜欢秘密，因此他可能会通过提出问题来揭开这个排列的奥秘。为了避免被猜透，Alice 决定与 Oscar 进行模拟训练。

这个模拟训练包括两个阶段：提问阶段和回答阶段。在提问阶段，Alice 需要回答一些关于这个排列的问题。接下来，在回答阶段，Alice 必须构造出两个满足所有提问的排列 $a_1, a_2, \ldots, a_N$ 和 $b_1, b_2, \ldots, b_N$。

在提问阶段，Oscar 会提出一系列问题，而你需要逐一作答。最开始时，Oscar 的体力 $S$ 是 $2N$。每个问题的提问都会消耗一些体力。问题分为以下 3 种类型：

• 类型 $1$：给出三个不同的整数 $i, j, k$，你需要回答整数 $a_i, a_j, a_k$ 的中位数 $m$。$m$ 必须在 $1$ 到 $N$ 的范围内。回答这个问题后，Oscar 的体力 $S$ 减少 $2$。
• 类型 $2$：给出两个不同的整数 $i, j$。如果 $a_i < a_j$，则回答 $i$；如果 $a_i > a_j$，则回答 $j$。回答这道题时会使 Oscar 的体力 $S$ 减少 $2$。
• 类型 $3$：给出两个不同的整数 $i, j$。你需要回答 $a_i$ 和 $a_j$ 中的最小值 $x$。$x$ 必须在 $1$ 到 $N$ 的范围内。回答此题时，Oscar 的体力 $S$ 减少 $1$。

所有问题必须作答。此外，Oscar 不会让自己过于疲惫，因此 每次提问后，Oscar 的体力余额 $S$ 不得低于 $2$。

提问阶段结束后，进入回答阶段。

在回答阶段，你需要提供两个从 $1$ 到 $N$ 的排列 $a_1, a_2, \ldots, a_N$ 和 $b_1, b_2, \ldots, b_N$。这两个排列必须满足提问阶段的所有回答，并且需要满足 $a_i \neq b_i$ 的 $i$ 的数量至少为 $\left\lceil \frac{S}{2} \right\rceil$（其中 $S$ 是提问结束后Oscar 剩余的体力）。如果你能实现这个条件，Alice 就赢得了胜利。事实上，总是可以找到这样的两个排列。

对 Alice 来说，找到让 Oscar 混乱的这两个排列非常有挑战性，她因此感到沮丧。请编写一个程序，确保无论 Oscar 提出什么问题，都能生成这两个让 Oscar 迷惑的排列，帮助 Alice 恢复信心。

输入格式

最初，输入一个整数 $N$，表示排列的大小。

$ N $

然后，输入将是一系列问题或者进入回答阶段的指令符号。

每种问题类型及其回答的格式如下：

类型 $1$ 的问题：

? $ 1 $ $ i $ $ j $ $ k $

其中 $i, j, k$ 是 $1$ 到 $N$ 的相异整数。

回答格式：

$ m $

其中 $m$ 是 $1$ 到 $N$ 之间的整数，是 $a_i, a_j, a_k$ 的中位数，同时也是 $b_i, b_j, b_k$ 的中位数。末尾需换行。

类型 $2$ 的问题：

? $ 2 $ $ i $ $ j $

其中 $i, j$ 是 $1$ 到 $N$ 的不同整数。

回答格式：

$ p $

这里 $p$ 是 $i$ 或 $j$，如果 $p = i$，则 $a_i < a_j$ 并且 $b_i < b_j$；如果 $p = j$，则 $a_i > a_j$ 并且 $b_i > b_j$。末尾需换行。

类型 $3$ 的问题：

? $ 3 $ $ i $ $ j $

其中 $i, j$ 是 $1$ 到 $N$ 的不同整数。

回答格式：

$ x $

$x$ 必须满足 $x = \min(a_i, a_j) = \min(b_i, b_j)$。末尾需换行。

如果进入回答阶段，输入格式为：

!

然后，你需要输出两个排列，格式如下：

$ a_1 $ $ a_2 $ $ \cdots $ $ a_N $ $ b_1 $ $ b_2 $ $ \cdots $ $ b_N $

当 Oscar 的剩余体力为 $S$ 时，序列 $a_i \neq b_i$ 上的 $i$ 个数要至少为 $\left\lceil \frac{S}{2} \right\rceil$。在输出两个排列后，程序必须立即终止，否则评判结果不确定。

注意，在每次输出后需要刷新缓冲区。例如，在 C 中可以使用：

printf("%d\n", m); fflush(stdout);

在 C++ 中可以使用：

cout << m << endl;

输出格式

见输入格式。

数据范围与提示

• $4 \leq N \leq 5 \times 10^4$
• $N$ 是整数

示例

以下是一个可能的输入输出示例。

解答程序的输出	解答程序的输入	说明
5		排列的大小为 5，Bob 的体力为 10。
	? 1 1 2 3	类型 1 的问题，Bob 的体力变为 8。
4		满足 $a_1, a_2, a_3$ 的中位数是 4 的排列符合要求。
	? 2 2 4	类型 2 的问题，Bob 的体力变为 6。
4		满足 $a_2 > a_4$ 的排列符合要求。
	? 3 4 5	类型 3 的问题，Bob 的体力变为 5。
1		满足 $\min(a_4, a_5) = 1$ 的排列符合要求。
	!	进入回答阶段。
3 5 4 1 2		提供了两个排列 "3, 5, 4, 1, 2" 和 "5, 4, 3, 2, 1"。
5 4 3 2 1		这两个排列符合所有问题的回答，并且有至少 3 个位置不同，因此是可以接受的答案。这只是一个例子，并不意味着特定的意义。

本翻译由 AI 自动生成