#P19004. 隐藏次序

隐藏次序

隐藏次序

时间限制:1 秒 空间限制:1024 MiB

这是一道交互题。

题目描述

有一个长度为 nn 的数组,每个元素只能是 0,1,20,1,2。你不知道各个元素的值。

一次询问指定两个下标 i,ji,j,交互器返回命题 ai>aja_i>a_j 是否成立:成立返回 11,否则返回 00。

你需要输出 1,2,…,n1,2,\ldots,n 的一个排列 pp,使对应的数组元素按非降顺序排列:

ap1≤ap2≤⋯≤apn.a_{p_1}\le a_{p_2}\le\cdots\le a_{p_n}.

每个测试用例至多允许询问 2n−32n-3 次。

交互器可以自适应作答。 隐藏数组不必在交互开始前确定,但此前所有回答必须始终与至少一个合法数组相容。你的最终排列必须对与全部回答相容的每一个数组都成立。

交互流程

程序开始时,读取整数 TT。每个测试用例开始时,读取整数 nn。

询问时输出一行:

? i j

然后读取一个整数 00 或 11。其中 1≤i,j≤n1\le i,j\le n。允许 i=ji=j,也允许重复询问,但都计入次数限制。

确定答案后输出一行:

! p_1 p_2 ... p_n

每个下标必须恰好出现一次。输出答案不计入询问次数。答案正确后,交互器不额外发送确认信息;若还有测试用例,直接读取下一个 nn。

每次输出询问或答案后,必须换行并刷新缓冲区。例如,C++ 可使用 cout << endl,或换行后调用 cout.flush()。

发生非法询问、超过次数限制、输出错误答案或格式错误时,交互器会结束运行,不再发送回答。若读取失败,你的程序应立即退出。

交互示例

以下是一段合法交互。横线仅用于分隔表格,不属于实际输入输出。

交互器发送 选手程序发送
2
3
? 1 2
1
? 2 3
1
! 3 2 1
2
? 1 2
0
! 1 2

数据范围与评分

1≤T≤2501\le T\le250,2≤n≤5002\le n\le500,每个测试文件内所有 nn 的和不超过 500500。

分组 分值 额外条件
1 20 n≤5n\le5
2 30 n≤50n\le50
3 50 无额外条件

各组均使用同一交互协议及 2n−32n-3 次询问限制。每组内全部测试文件通过,才获得该组分数。

本地测试

本题不能把隐藏测试文件直接重定向给选手程序。请使用随卷提供的本地交互工具连接你的程序与交互器,操作见 交互题本地测试说明.md。

[下载交互题本地工具](file://交互题本地工具.zip)


题目原作:电子科技大学命题组,2026 ICPC 成都区域赛。中文整理及本校评分分组已作调整;题面遵循 CC BY-SA 4.0。

下发文件

公开本地联测输入

本地交互工具

本题为交互题,请按工具包中的用法联测,勿将联测输入直接重定向给选手程序。