← 返回题目列表

AtCoder · kupc2020_l

L. 中值查询的内幕

中文机器翻译题面 查看原题

配点 : 500 点

問題文

这是交互元素的问题。

爱丽丝是 我隐藏了 1 减去 N 以内的整数排列。爱丽丝有一个朋友,名叫鲍勃。鲍勃讨厌秘密,因此我们可以期望他提出问题来尝试识别这种排列。为了回避问题,避免被认出,爱丽丝决定和奥斯卡一起进行模拟演练。

模拟训练由提问阶段和回答阶段组成。在提问阶段,Alice 必须回答一些有关排列的问题。在随后的回答阶段,与问题答案一致的排列是 必须配置 a_1, a_2, \ldots, a_N 该值应乘以 2 。

在提问阶段,您会遇到几个问题,请按顺序回答。最初,奥斯卡的体力 S 是 您也可以写 2N 并且每次提问都会消耗体力。对于问题 3 有多种类型,其格式如下。

  • 类型 1: 3 两个不同的整数 应为 i,j,k 。 表示3 整数 a_i,a_j,a_k 中位数的整数 回答 m 。 必须小于或等于m 是 您也可以写 1 以上 N 。当你问这个问题时奥斯卡的耐力 S 是 您也可以写 2 减少。

  • 类型 2: 2 两个不同的整数 i,j 。 表示a_i < a_j 应该是 回答 i ,a_i > a_j 应该是 回答 j 。当你问这个问题时奥斯卡的耐力 S 是 您也可以写 2 减少。

  • 类型 3: 2 两个不同的整数 i,j 。 表示a_i,a_j 最小值的整数 x 。 必须小于或等于x 是 您也可以写 1 以上 N 。当你问这个问题时奥斯卡的耐力 S 是 您也可以写 1 减少。

所有问题都必须得到回答。而且,奥斯卡也累了。 奥斯卡提问后的体力 它不能小于 S 是 在 2 。

提问阶段结束后,回答阶段开始。

在回答阶段, 直到2 个 1 减去 N 到 a_1, a_2, \ldots, a_N 和 按字典顺序比较 b_1, b_2, \ldots, b_N 交给奥斯卡。这个 2 排列是与每个问题阶段的所有答案一致的排列,a_i \neq b_i 变为 i 的数量是 如果您对小于或等于 \left\lceil \frac{S}{2} \right\rceil 任何高于此的内容都会让奥斯卡感到困惑。这里 S 是奥斯卡做完所有题目后的体力。奥斯卡看起来很困惑。 如果 Alice 能说出 2 排列,她就获胜。像这样 我们可以证明我们可以构造 2 排列。

爱丽丝觉得奥斯卡很困惑。 2 找到一种排列非常困难,我很沮丧。无论提出什么问题,奥斯卡都显得很困惑。 编写一个程序,打印 2 排列来让 Alice 高兴起来。

制約

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

入出力

第一个排列大小 N 是 在 1 行中给出。

N

然后输入 给出一个 1,2,3 问题或代表回答阶段开始的符号作为输入。

类型 1 问题按以下格式给出。 不超过

? 1 i j k

i,j,k 是 您也可以写 1 减去 N 的不同整数。

接下来,按以下格式输出问题的答案。 必须是

m

m 是 您也可以写 1 减去 N 以内的整数。此外,这 a_i,a_j,a_k 可以得到第 3 是整数的中位数,b_i,b_j,b_k 可以得到第 3 必须是两个整数的中位数。最后输出换行符。 必须是

类型 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) 。最后输出换行符。

当进入回答阶段时,代表回答阶段开始的符号以以下格式给出。

!

此后, 2 排列。

a_1 a_2 \cdots a_N
b_1 b_2 \cdots b_N

鲍勃的剩余体力 S 时,排列 a_i \neq b_i 变为 i 的数量是 如果您对小于或等于 \left\lceil \frac{S}{2} \right\rceil 还需要更多。最后输出换行符。 2 排列后,您的程序必须立即退出。如果测试没有完成,判断结果是不确定的。

另外,以这些以外的格式输出时的判断结果也是未定义的。

请注意,您需要在每次输出后刷新输出。例如,输入 在回答问题 1 时,用C语言

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

在 C++ 中 只需输出

cout<<m<<endl;

。

入出力例

可以进行以下输入/输出。

应答程序的输出 输入应答程序 説明
5 排列的大小 5 作为输入给出。鲍勃的体力是 10 。
? 1 1 2 3 类型 1 提出问题。鲍勃的体力是 8 变为。
4 a_1, a_2, a_3 的中值为 4 的排列与此问题匹配。 排列
? 2 2 4 类型 2 提出问题。鲍勃的体力是 6 变为。
4 a_2 > a_4 与这个问题匹配。
? 3 4 5 类型 3 提出问题。鲍勃的体力是 5 变为。
1 \min(a_4, a_5)=1 与这个问题匹配。
! 进入答题阶段。
3 5 4 1 2
5 4 3 2 1
两种排列 "3,5,4,1,2“和” 输出5,4,3,2,1“。这与提问阶段的所有答案是一致的, 答案是正确的,因为至少\lceil 5/2 \rceil = 3 元素是不同的。

这只是输入/输出的示例,并不一定意味着有意义的输入/输出。