#P19004. 隐藏次序
隐藏次序
隐藏次序
时间限制:1 秒 空间限制:1024 MiB
这是一道交互题。
题目描述
有一个长度为 的数组,每个元素只能是 。你不知道各个元素的值。
一次询问指定两个下标 ,交互器返回命题 是否成立:成立返回 ,否则返回 。
你需要输出 的一个排列 ,使对应的数组元素按非降顺序排列:
每个测试用例至多允许询问 次。
交互器可以自适应作答。 隐藏数组不必在交互开始前确定,但此前所有回答必须始终与至少一个合法数组相容。你的最终排列必须对与全部回答相容的每一个数组都成立。
交互流程
程序开始时,读取整数 。每个测试用例开始时,读取整数 。
询问时输出一行:
? i j
然后读取一个整数 或 。其中 。允许 ,也允许重复询问,但都计入次数限制。
确定答案后输出一行:
! p_1 p_2 ... p_n
每个下标必须恰好出现一次。输出答案不计入询问次数。答案正确后,交互器不额外发送确认信息;若还有测试用例,直接读取下一个 。
每次输出询问或答案后,必须换行并刷新缓冲区。例如,C++ 可使用 cout << endl,或换行后调用 cout.flush()。
发生非法询问、超过次数限制、输出错误答案或格式错误时,交互器会结束运行,不再发送回答。若读取失败,你的程序应立即退出。
交互示例
以下是一段合法交互。横线仅用于分隔表格,不属于实际输入输出。
| 交互器发送 | 选手程序发送 |
|---|---|
2 |
|
3 |
|
? 1 2 |
|
1 |
|
? 2 3 |
|
1 |
|
! 3 2 1 |
|
2 |
|
? 1 2 |
|
0 |
|
! 1 2 |
数据范围与评分
,,每个测试文件内所有 的和不超过 。
| 分组 | 分值 | 额外条件 |
|---|---|---|
| 1 | 20 | |
| 2 | 30 | |
| 3 | 50 | 无额外条件 |
各组均使用同一交互协议及 次询问限制。每组内全部测试文件通过,才获得该组分数。
本地测试
本题不能把隐藏测试文件直接重定向给选手程序。请使用随卷提供的本地交互工具连接你的程序与交互器,操作见 交互题本地测试说明.md。
[下载交互题本地工具](file://交互题本地工具.zip)
题目原作:电子科技大学命题组,2026 ICPC 成都区域赛。中文整理及本校评分分组已作调整;题面遵循 CC BY-SA 4.0。
下发文件
本题为交互题,请按工具包中的用法联测,勿将联测输入直接重定向给选手程序。
相关
在下列比赛中: