CF1552G A Serious Referee

Andrea 想出了一个他认为新颖的长度为 $n$ 的数组排序算法。该算法的工作方式如下： 最初有一个包含 $n$ 个整数 $a_1,\, a_2,\, \dots,\, a_n$ 的数组。然后，执行 $k$ 步操作。 对于每一步 $1\le i\le k$，在第 $i$ 步中，对数组 $a$ 的下标为 $j_{i,1}< j_{i,2}< \dots< j_{i, q_i}$ 的子序列进行排序，其余下标对应的值不变。也就是说，将子序列 $a_{j_{i,1}},\, a_{j_{i,2}},\, \dots,\, a_{j_{i,q_i}}$ 排序，数组中的其他元素保持不变。 Andrea 迫不及待地想与学术界分享他的发现，于是向期刊“Annals of Sorting Algorithms”投递了一篇简短的论文描述他的算法，而你正是这篇论文的审稿人（即需要判断论文正确性的人）。你需要判断 Andrea 的算法是否正确，也就是说，对于任意长度为 $n$ 的整数数组 $a$，算法结束后数组 $a$ 是否一定有序。

第一行包含两个整数 $n$ 和 $k$（$1\le n\le 40$，$0\le k\le 10$），分别表示 Andrea 算法处理的数组长度和操作步数。 接下来有 $k$ 行，每行描述 Andrea 算法某一步中考虑的子序列。 第 $i$ 行包含一个整数 $q_i$（$1\le q_i\le n$），后跟 $q_i$ 个整数 $j_{i,1},\,j_{i,2},\,\dots,\, j_{i,q_i}$（$1\le j_{i,1}

如果 Andrea 的算法是正确的，输出 ACCEPTED，否则输出 REJECTED。

第一个样例说明： 算法包含 $3$ 步。第一步排序子序列 $[a_1, a_2, a_3]$，第二步排序子序列 $[a_2, a_3, a_4]$，第三步排序子序列 $[a_1,a_2]$。例如，初始时 $a=[6, 5, 6, 3]$，算法的变化过程如下（被排序的子序列用红色高亮） $$ [{\color{red}6},{\color{red}5},{\color{red}6},3] \rightarrow [5, {\color{red}6}, {\color{red}6}, {\color{red}3}] \rightarrow [{\color{red}5}, {\color{red}3}, 6, 6] \rightarrow [3, 5, 6, 6] $$ 可以证明，对于任意初始数组 $a$，算法结束后数组 $a$ 都是有序的。 第二个样例说明： 算法包含 $3$ 步。第一步排序子序列 $[a_1, a_2, a_3]$，第二步排序子序列 $[a_2, a_3, a_4]$，第三步排序子序列 $[a_1,a_3,a_4]$。例如，初始时 $a=[6, 5, 6, 3]$，算法的变化过程如下（被排序的子序列用红色高亮） $$[{\color{red}6},{\color{red}5},{\color{red}6},3] \rightarrow [5, {\color{red}6}, {\color{red}6}, {\color{red}3}] \rightarrow [{\color{red}5}, 3, {\color{red}6}, {\color{red}6}] \rightarrow [5, 3, 6, 6]$$ 注意 $a=[6,5,6,3]$ 就是一个不会被该算法排好序的例子。 第三个样例说明： 算法包含 $4$ 步。前 $3$ 步都没有作用，因为它们排序的都是长度为 $1$ 的子序列，而第四步排序子序列 $[a_1,a_3]$。例如，初始时 $a=[5,6,4]$，算法的变化过程如下（被排序的子序列用红色高亮） $$[{\color{red}5},6,4] \rightarrow [5,{\color{red}6},4] \rightarrow [5,{\color{red}6},4] \rightarrow [{\color{red}5},6,{\color{red}4}]\rightarrow [4,6,5]$$ 注意 $a=[5,6,4]$ 就是一个不会被该算法排好序的例子。 第四个样例说明： 算法包含 $2$ 步。第一步排序子序列 $[a_2,a_3,a_4]$，第二步排序整个数组 $[a_1,a_2,a_3,a_4,a_5]$。例如，初始时 $a=[9,8,1,1,1]$，算法的变化过程如下（被排序的子序列用红色高亮） $$[9,{\color{red}8},{\color{red}1},{\color{red}1},1] \rightarrow [{\color{red}9},{\color{red}1},{\color{red}1},{\color{red}8},{\color{red}1}] \rightarrow [1,1,1,8,9]$$ 由于最后一步对整个数组进行了排序，因此对于任意初始数组 $a$，算法结束后数组 $a$ 一定是有序的。 由 ChatGPT 4.1 翻译