← 返回题目列表

AtCoder · kupc2020_j

J. 中值查询

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

配点 : 400 点

問題文

这是交互元素的问题。

爱丽丝是 我隐藏了 1 减去 N 到的整数的排列组合 a_1, a_2, \ldots, a_N 藏了起来。鲍勃不喜欢秘密,并希望以某种方式识别这种排列。 Alice想尽可能隐藏这个排列。 N 及以下 2 它只会告诉您一类问题的答案。

  • 类型 1: 3 两个不同的整数 i,j,k(1 \leq i,j,k \leq N) 并询问 Alice。然后爱丽丝 a_i,a_j,a_k 可以得到第 3 找到两个整数的中位数。 找到
  • 类型 2: 2 两个不同的整数 i,j(1 \leq i,j \leq N) 并询问 Alice。然后爱丽丝 a_i, a_j 的较小下标。换句话说,a_i < a_j 如果 i,否则 回答 j 。

然而,Alice 不想给出太多的排列信息,所以类型 对于 1 问题: 2N 次,类型 我只会回答 2 问题: 2 次。此外,Alice 很挑剔,可能会改变排列的顺序,只要它们不与 Bob 对之前问题的回答相矛盾即可。

鲍勃太忙,无暇思考和提问。通过编写一个提出问题和猜测排列的程序来帮助鲍勃。

制約

  • 4 \leq N \leq 6 \times 10^4

部分点

  • 类型 1 的最大问题数是 3N 次,类型 我只会回答 2 的最大问题数是 3 次。如果你问的问题超出了这个限制, 超出查询限制 变为。
  • 当题数没有超过上限并且输出正确的排列时,20 点。
  • 类型 1 问题 2N 次内并输入 如果您在 2 问题 2 次内输出正确的排列,您将获得满分。

入出力

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

N

类型 1 问题时,请按照以下格式输出。 必须是

? 1 i j k

i,j,k 是 您也可以写 1 减去 N 以内的不同整数。最后输出换行符。 问题

类型 1 的答案按以下格式给出。 最大为

m

m 是 您也可以写 1 减去 N 的整数。这是 a_i,a_j,a_k 可以得到第 3 是两个整数的中位数。 输出

类型 2 问题时,请按照以下格式输出。 必须是

? 2 i j

i,j 是 您也可以写 1 减去 N 以内的不同整数。最后输出换行符。 问题

类型 2 的答案按以下格式给出。 最大为

k

k 是 您也可以写 i 或 至少 j 。a_i < a_j 如果 i,否则 回答 j 。

类型 1 的最大问题数是 3N 次,类型 我只会回答 2 的最大问题数是 3 次。如果你问的问题超出了这个限制, 超出查询限制 变为。

提出几个问题后,您需要猜测排列。此时,请按照以下格式输出。

! a_1 a_2 a_3 \cdots a_N

打印排列后,您的程序必须立即退出。如果测试没有完成,判断结果是不确定的。

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

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

printf("? 1 %d %d %d\n", i, j, k); fflush(stdout);

在 C++ 中 只需输出

cout<<"? 1 "<<i<<" "<<j<<" "<<k<<endl;

。

请注意,有些测试用例的排列从一开始就不是固定的。

入出力例

排列是“3,5,4,1,2”,可以进行以下输入/输出。

应答程序的输出 输入应答程序 説明
5 排列的大小 5 作为输入给出 问
? 1 1 2 3 类型 1 问题, 收听a_1, a_2, a_3 的中值
4 a_1, a_2, a_3 的中值为 4 是
? 2 2 4 类型 2 问题, 收听a_2 和 按字典顺序比较 a_4 所以我问哪一个更小。
4 a_2 > a_4 ,所以 给出4 被给予
? 1 1 5 4 类型 1 问题, 收听a_1, a_5, a_4 的中值
2 a_1, a_5, a_4 的中值为 2 是
! 3 5 4 1 2 排列是“3,5,4,1,2“

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