#P12580. [UOI 2021] 猜排列【交互题暂未配置】

    ID: 14148 远端评测题 30000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2021交互题Special JudgeUOI(乌克兰)

[UOI 2021] 猜排列【交互题暂未配置】

题目描述

请注意本题不寻常的时间限制。

给定一个由 nn 个数字组成的排列(nn 是 2 的幂次)。排列中元素的顺序对你来说是未知的。

排列是指长度为 nn 的整数序列,包含从 11nn 的所有数字,每个数字恰好出现一次。例如,[1][1][4,3,5,1,2][4, 3, 5, 1, 2][3,2,1][3, 2, 1] 是排列,而 [1,1][1, 1][4,3,1][4, 3, 1][2,3,4][2, 3, 4] 不是。

此外,存在一种查询方式:你可以提供一个长度为 nn 的数组 aa,满足 1ain1 \le a_i \le n(注意 aa 不一定是排列)。作为响应,你会得到一个长度为 nn 的数组 cc,其生成规则如下:

c = 长度为 n 的全零数组
for i = 1 to n:
    if p[a[i]] > p[i]:
         c[a[i]] += 1
返回 c

你的任务是找出隐藏的排列 pp。最大查询次数请参见“评分”部分。

输入格式

第一行包含两个整数 ttqq1t,q2561 \le t, q \le 256)——分别是测试用例的数量和每个测试用例允许的最大查询次数。

交互说明

对于每个测试用例,首先读取一个整数 nn1n10241 \le n \le 1024),表示排列 pp 的长度。

保证 nn 是 2 的幂次(即存在非负整数 kk 使得 2k=n2^k = n)。

要发起查询,请输出 1 a1 a2 an1\ a_1\ a_2 \dots \ a_n1ain1 \le a_i \le n)。

作为响应,评测系统会返回数组 cc,其生成规则如题目描述所示,格式为 c1 c2  cnc_1\ c_2\ \dots \ c_n

发起查询后,请确保输出换行符并刷新输出缓冲区,否则可能触发“超出时间限制”错误。刷新缓冲区的方法如下:

  • C++:fflush(stdout)cout.flush()
  • Java:System.out.flush()
  • Pascal:flush(output)
  • Python:stdout.flush()

其他语言请参考相关文档。

注意:如果你的查询无效(超过查询次数限制或数组 aa 不满足条件),评测系统会返回 1-1 并终止程序。如果读取到 1-1,请立即终止程序以避免意外结果。

当你确定排列 pp 后,请输出 2 p1 p2 pn2\ p_1\ p_2 \dots \ p_n

如果是最后一个测试用例,程序应终止;否则继续处理下一个测试用例。

输出格式

见交互说明。

1 256
4

0 1 1 1

1 3 2 4 2

2 1 4 2 3

提示

说明

从第一次查询可知 p1<p3<p4<p2p_1 < p_3 < p_4 < p_2

因此,所求排列为 [1,4,2,3][1, 4, 2, 3]

评分

qq 表示程序允许的最大查询次数。

  • (3 分)n16n \le 16q=256q=256t=128t=128
  • (7 分)n32n \le 32q=256q=256t=128t=128
  • (8 分)n256n \le 256q=256q=256t=128t=128
  • (14 分)n512n \le 512q=256q=256t=128t=128
  • (20 分)n512n \le 512q=128q=128t=256t=256
  • (最高 48 分)n1024n \le 1024q=127q=127t=256t=256;设 kk 为单个测试用例中实际使用的最大查询次数,则得分规则为:
    • k>127k > 127,得 0 分;
    • 55<k12755 < k \le 127,得 4824(k55)3748 - \lceil \frac{24(k-55)}{37} \rceil 分;
    • k55k \le 55,得 48 分;

翻译由 DeepSeek V3 完成