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 中可以使用：
```c
printf("%d\n", m); fflush(stdout);
```
在 C++ 中可以使用：
```cpp
cout
输入格式
无
输出格式
无
说明/提示
### 制約
- $ 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 $
$ 5 $ $ 4 $ $ 3 $ $ 2 $ $ 1 $ 2 つの順列 "$ 3,5,4,1,2 $" と "$ 5,4,3,2,1 $" を出力している。これは共に質問フェーズでのすべての回答に矛盾せず、$ \lceil\ 5/2\ \rceil\ =\ 3 $ 個以上の要素が異なるので正解となる。これは入出力の一つの例であり、意味のある入出力をしているとは限らない。