P15886 [ICPC 2026 NAC] Leaking Santa' s Secrets

圣诞节到了！当大多数工作场所都在参与“秘密圣诞老人”礼物交换时，你的工作场所却在酝酿一个更邪恶的计划：揭露圣诞老人的秘密。 圣诞老人有一份地球上每个人的“淘气或乖巧”名单。由于其内容极其敏感，这份名单是用北极语写成的，这是一种包含 $N$ 个字母的神秘语言。为了进一步确保安全，圣诞老人用 **替换密码** 对这份名单进行了加密：一个对数字 $1, 2, \ldots, N$ 的排列 $H$，它将每个北极语字母 $i$ 映射到一个不同的字母 $H(i)$。在这种密码中，没有两个字母会映射到同一个目标字母——形式化地说，如果 $i \neq j$，则 $H(i) \neq H(j)$——否则圣诞老人将无法解密他的名单！（圣诞老人可以选择将某些字母映射到自身，即 $H(i) = i$，这只是为了增加迷惑性。） 对你来说幸运的是，圣诞老人的服务器由于编写糟糕而暴露在公共互联网上。你和你的同事希望能入侵圣诞老人的服务器，解密他的名单，并确认你们都很淘气！（黑客总是淘气的。） 该服务器的设计使得圣诞老人可以随时快速检查他的名单。当用户连接到服务器后，它会提示用户输入由 $N$ 个整数 $H(1), H(2), \ldots, H(N)$ 组成的列表（编码了排列 $H$），验证该列表是否正确，然后解密圣诞老人的秘密名单。 经过数月的研究，你发现了一个侧信道时序漏洞。假设你输入一个排列 $Q$。如果 $H = Q$，则服务器立即授予访问权限。否则，考虑一个包含 $N$ 个顶点的图，并为每个顶点 $i$ 添加一条从 $i$ 指向 $H(Q(i))$ 的边。你发现服务器的复杂身份验证算法会返回一个“访问被拒绝”的错误消息，其响应时间恰好等于结果图中连通分量的个数。 例如，假设 $N = 4$，且密码排列 $H$ 如下： $$ \begin{array}{|c|c|c|c|c|} i & 1 & 2 & 3 & 4\\ H(i) & 2 & 3 & 1 & 4 \end{array} $$ 如果你尝试用输入 $\texttt{4 3 2 1}$ 登录服务器，由于该排列与 $H$ 不匹配，并且上述描述的图有两个连通分量（一个包含边 $1 \to 4 \to 2 \to 1$ 形成的环，另一个仅包含自环 $3 \to 3$），服务器将在延迟 $2$ 秒后返回“访问被拒绝”的错误消息。 请注意，如果你多次使用不同的输入 $Q$ 尝试登录服务器，每次都会针对 **同一个** 存储的 $H$ 进行认证。服务器不会根据你的输入以任何方式改变 $H$。 如果圣诞老人发现他的服务器被未经授权的请求轰炸，他会起疑心。你估计最多只能进行 $1510$ 次登录尝试，否则会引起太多怀疑。你能找到一种有效的策略来确定密码排列吗？ ### 交互方式 本题为交互题。交互开始时，从标准输入读取一个整数 $N$ $(1 \leq N \leq 220)$，表示北极语字母的数量。评测器是非自适应的：隐藏的排列 $H$ 在此刻被选定，并在交互的其余部分保持不变。 要尝试登录服务器，请输出一行，包含 $N$ 个空格分隔的整数 $Q(1), \ldots, Q(N)$，其中 $Q$ 是 $\{1, 2, \ldots, N\}$ 的一个排列。然后从标准输入读取一个整数，表示服务器对你的输入做出响应的秒数。 如果该延迟为 $0$，则表示你已成功找到密码排列 $H$，程序应终止。否则，该延迟即为按照上述过程构建的图中的连通分量数。 你最多可以尝试登录 $1510$ 次。如果尝试次数用尽，程序应干净退出（尽管你会因未能解密圣诞老人的“淘气或乖巧”名单而被判为错误）。

无

无

### 注意 **在每行输出后请勿忘记刷新输出缓冲区**，并在交互结束后干净退出。同时，请务必严格按照上述交互协议的要求输出对应行上的信息：例如，如果协议要求你在单行输出空格分隔的整数列表，评测器 **不会** 接受每个整数单独占一行的情况。 如果评测器接收到无效或意外的输入，它将输出 $-1$ 并立即退出。你的程序必须检测到此情况并干净退出，以便得到 Wrong Answer 的评测结果。如果你的程序阻塞等待与评测器的进一步交互，或试图将 $-1$ 解释为连通分量数，你可能会收到其他被拒的评测结果（如 Time Limit Exceeded 或 Runtime Error）而不是 Wrong Answer。 已为你提供用于本地测试的命令行工具。该工具顶部有注释说明其使用方法。 翻译由 DeepSeek V3.2 完成