← 返回题目列表

Codeforces · 1552/G

G. 一位严肃的裁判

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

Andrea 提出了一种他认为是针对长度 $$$n$$$ 的数组的新颖排序算法。该算法的工作原理如下。

最初有一个 $$$n$$$ 整数数组 $$$a_1,\, a_2,\, \dots,\, a_n$$$。然后,执行 $$$k$$$ 步骤。

对于每个 $$$1\le i\le k$$$,在第 $$$i$$$ 步骤中,对索引为 $$$j_{i,1}< j_{i,2}< \dots< j_{i, q_i}$$$ 的数组 $$$a$$$ 的子序列进行排序,而不更改其余索引的值。因此,子序列 $$$a_{j_{i,1}},\, a_{j_{i,2}},\, \dots,\, a_{j_{i,q_i}}$$$ 已排序,并且 $$$a$$$ 的所有其他元素保持不变。

Andrea 急于与学术界分享他的发现,向《排序算法年鉴》杂志发送了一篇描述他的算法的短论文,而你是这篇论文的审稿人(即必须判断论文正确性的人)。您必须确定 Andrea 的算法是否正确,即它是否对 $$$n$$$ 整数的任意数组 $$$a$$$ 进行排序。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1\le n\le 40$$$, $$$0\le k\le 10$$$) — Andrea 算法处理的数组长度和 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}<j_{i,2}<\cdots<j_{i,q_i}\le n$$$) — 第 $$$i$$$ 步骤中考虑的子序列的长度以及子序列的索引。

输出

如果 Andrea 的算法正确,则打印 ACCEPTED,否则打印 REJECTED。

示例

输入 #1

4 3
3 1 2 3
3 2 3 4
2 1 2

输出 #1

ACCEPTED

输入 #2

4 3
3 1 2 3
3 2 3 4
3 1 3 4

输出 #2

REJECTED

输入 #3

3 4
1 1
1 2
1 3
2 1 3

输出 #3

REJECTED

输入#4

5 2
3 2 3 4
5 1 2 3 4 5

输出#4

ACCEPTED

注意

第一个示例的说明:该算法由 $$$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$$$ 将被排序。