← 返回题目列表

AtCoder · arc218_c

C. 阿弥陀寺

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

准备尽可能少的天梯彩票类型,并将它们组合起来,以便可以产生所有排列。

这是一个 交互问题 (其中您的程序和判断程序通过输入和输出进行交互)。

给你一个正整数 N.

选择任何正整数 m 和 m 的排列 (1,2,\dots,N),并输出它们。让 i-th 排列为 P_i=(P_{i,1},P_{i,2},\dots,P_{i,N}).

然后,一个排列 给出了 Q=(Q_1,Q_2,\dots,Q_N) of (1,2,\dots,N) 。输出正整数序列 A=(A_1,A_2,\dots,A_k) 满足以下所有条件。

  • 0 \le k \le 2N^2
  • 的所有元素 A 之间 1 和 m,包括在内。
  • 从序列开始 R=(1,2,\dots,N),执行以下操作 i = 1,2,\dots,k 按顺序导致 R = Q.
    • 让 p = P_{A_i}。同时更换 R_{j} 与 R_{p_j} 对于每个 j = 1,2,\dots,N.

让 m_{\min} 是最小值 m 无论怎样都可以解决上述问题 Q。你的输出 m 必须等于 m_{\min}.

更准确地说 对于一系列排列 P=(P_1,P_2,\dots,P_m) of (1,2,\dots,N),我们称之为 P a 良好的排列顺序 如果满足以下条件:
  • 对于任何排列 Q=(Q_1,Q_2,\dots,Q_N) of (1,2,\dots,N),存在正整数序列 A=(A_1,A_2,\dots,A_k) 满足以下所有条件。
    • 0 \le k \le 2N^2
    • 的所有元素 A 之间 1 和 m,包括在内。
    • 从序列开始 R=(1,2,\dots,N),执行以下操作 i = 1,2,\dots,k 按顺序导致 R = Q.
      • 让 p = P_{A_i}。同时更换 R_{j} 与 R_{p_j} 对于每个 j = 1,2,\dots,N.
保证至少有一个 良好的排列顺序 存在。因此,最小值 m_{\min} 的长度 m 的 良好的排列顺序 已确定。你的输出 m 必须等于 m_{\min}.
请注意您的输出 P 不需要是 良好的排列顺序。如果您能输出一个,则认为您的提交是正确的 A 满足给定的条件 Q.

约束

  • 3 \le N \le 500
  • Q 是一个排列 (1,2,\dots,N).
  • 所有输入值均为整数。

输入/输出

这是一个 交互问题 (其中您的程序和判断程序通过输入和输出进行交互)。

首先,法官给你一个正整数 N 采用以下格式:

N

然后,输出你选择的正整数 m 和 m 的排列 (1,2,\dots,N) 格式如下 m+1 行。在这里, j- 第一个元素 i-th 排列是 P_{i,j}。确保在最后输出换行符。

m
P_{1,1}\ P_{1,2}\ \dots\ P_{1,N}
P_{2,1}\ P_{2,2}\ \dots\ P_{2,N}
\vdots
P_{m,1}\ P_{m,2}\ \dots\ P_{m,N}

必须满足以下条件:

  • m \le 1000
  • (P_{i,1},P_{i,2},\dots,P_{i,N}) 是一个排列 (1,2,\dots,N).

如果你的输出 P 不满足上述条件,则判断输出 -1。此时,您的提交已被判定为不正确。判断程序将在此时终止,因此建议您的程序也终止。

然后,法官给你一个排列 Q=(Q_1,Q_2,\dots,Q_N) of (1,2,\dots,N) 采用以下格式:

Q_1\ Q_2\ \dots\ Q_N

然后,输出一个正整数序列 A=(A_1,A_2,\dots,A_k) 采用以下格式。确保在最后输出换行符。

k\ A_1\ A_2\ \dots\ A_k

当且仅当以下条件全部满足时,您的输出才会被判断为正确:

  • m = m_{\min}
  • 0 \le k \le 2N^2
  • 的所有元素 A 之间 1 和 m,包括在内。
  • 从序列开始 R=(1,2,\dots,N),执行以下操作 i = 1,2,\dots,k 按顺序导致 R = Q.
    • 让 p = P_{A_i}。同时更换 R_{j} 与 R_{p_j} 对于每个 j = 1,2,\dots,N.

注释

  • 在每个输出之后,插入换行符并刷新标准输出。如果不这样做,可能会导致法官做出以下判决: TLE.
  • 如果您收到 -1,立即终止您的程序。如果你这样做,法官的判决将是 WA,但如果你不这样做,法官的判决将是不确定的。
  • 输出答案后立即终止程序。否则,法官的判决将是不确定的。
  • 不要输出不必要的换行符,因为它们将被视为格式错误。
  • 这个问题的判断不是自适应的。判断程序决定 Q 在互动开始之前。

示例输入/输出

以下是一个案例 N=3,Q=(2,3,1).

输入 输出 说明
3 N 。
2
2 1 3
3 2 1
选择 m = 2,P_1=(2,1,3),P_2=(3,2,1) 并输出它们。
2 3 1 自从 P 满足条件, Q=(2,3,1) 。
2 2 1 A=(2,1) 满足条件。 R 变为 (1,2,3) \rightarrow (3,2,1) \rightarrow (2,3,1),匹配 Q.
另外, m_{\min} = 2 为 N = 3,和 m = m_{\min} 很满意。
因此,该输出被判断为正确。
一定要输出 k 也一样,都在一行上。