#P12580. [UOI 2021] 猜排列【交互题暂未配置】
[UOI 2021] 猜排列【交互题暂未配置】
题目描述
请注意本题不寻常的时间限制。
给定一个由 个数字组成的排列( 是 2 的幂次)。排列中元素的顺序对你来说是未知的。
排列是指长度为 的整数序列,包含从 到 的所有数字,每个数字恰好出现一次。例如,、、 是排列,而 、、 不是。
此外,存在一种查询方式:你可以提供一个长度为 的数组 ,满足 (注意 不一定是排列)。作为响应,你会得到一个长度为 的数组 ,其生成规则如下:
c = 长度为 n 的全零数组
for i = 1 to n:
if p[a[i]] > p[i]:
c[a[i]] += 1
返回 c
你的任务是找出隐藏的排列 。最大查询次数请参见“评分”部分。
输入格式
第一行包含两个整数 和 ()——分别是测试用例的数量和每个测试用例允许的最大查询次数。
交互说明
对于每个测试用例,首先读取一个整数 (),表示排列 的长度。
保证 是 2 的幂次(即存在非负整数 使得 )。
要发起查询,请输出 ()。
作为响应,评测系统会返回数组 ,其生成规则如题目描述所示,格式为 。
发起查询后,请确保输出换行符并刷新输出缓冲区,否则可能触发“超出时间限制”错误。刷新缓冲区的方法如下:
- C++:
fflush(stdout)
或cout.flush()
; - Java:
System.out.flush()
; - Pascal:
flush(output)
; - Python:
stdout.flush()
;
其他语言请参考相关文档。
注意:如果你的查询无效(超过查询次数限制或数组 不满足条件),评测系统会返回 并终止程序。如果读取到 ,请立即终止程序以避免意外结果。
当你确定排列 后,请输出 。
如果是最后一个测试用例,程序应终止;否则继续处理下一个测试用例。
输出格式
见交互说明。
1 256
4
0 1 1 1
1 3 2 4 2
2 1 4 2 3
提示
说明
从第一次查询可知 。
因此,所求排列为 。
评分
表示程序允许的最大查询次数。
- (3 分),,;
- (7 分),,;
- (8 分),,;
- (14 分),,;
- (20 分),,;
- (最高 48 分),,;设 为单个测试用例中实际使用的最大查询次数,则得分规则为:
- 若 ,得 0 分;
- 若 ,得 分;
- 若 ,得 48 分;
翻译由 DeepSeek V3 完成