QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 64 MB Total points: 100

#14647. Uczta

統計

Król Bajtazar 正在为自己 $128$ 岁生日举办盛大宴会。他决定将受邀宾客安排在圆桌旁就坐,使得没有任何宾客独自坐在一张桌旁。他已经选好了 $n$ 位可能邀请的人,并将他们按重要性从高到低排序,依次编号为 $1$ 到 $n$(编号为 $1$ 的宾客最重要)。

宾客们要求很高:每个人都向国王提出了关于“谁可以坐在他右侧”的要求。国王希望每位受邀宾客都有合适的同伴,因此不会允许任何一位宾客的要求未被满足。所以可能无法邀请全部 $n$ 个人。Bajtazar 请你(宫廷信息学家)求出在所有可能的受邀集合中“最好的”那个,并给出一种将他们安排在若干圆桌旁的示例方案。国王被问到“最好”是什么意思时,作为一位 $127$ 岁的信息学外行,他却出人意料地给出了相当严谨的定义:

为了比较两组宾客集合,我选择编号最小且只属于其中一个集合的人。这个人所在的集合就是更好的集合。

在这样定义的顺序下,确实可以唯一确定所有可能宾客集合中哪一个是最好的。

输入格式

第一行包含一个整数 $n$($2 \le n \le 2000$),表示宾客人数。在接下来的 $n$ 行中,第 $i$ 行描述编号为 $i$ 的人的偏好。偏好描述以一个整数 $k_i$($k_i \ge 0$)开头,随后给出 $k_i$ 个两两不同的人员编号——这些是从 $1$ 到 $n$ 的整数,且不等于 $i$。每个这样的编号表示一位可以坐在编号为 $i$ 的人右侧的宾客。所有 $k_i$ 之和不超过 $5000$。

在价值 $50%$ 分数的测试中,额外满足条件:若人员 $a$ 允许人员 $b$ 坐在其右侧,则人员 $b$ 也允许人员 $a$ 坐在其右侧。特别地,这意味着这两个人可以一起坐在同一张两人桌旁。

在价值 $20%$ 分数的测试中,可以邀请全部 $n$ 位宾客参加宴会。

输出格式

输出第一行应包含一个整数 $s$,表示方案中的桌子数量。接下来的 $s$ 行应描述每张桌子。每张桌子的描述以一个整数 $g$ 开头,表示该桌就坐的宾客人数。随后给出 $g$ 个整数表示这些宾客的编号。宾客编号应按逆时针方向依次给出。第一个输出的宾客将坐在最后一个输出的宾客的右侧。

样例数据

对于输入数据:

6
3 2 6 3
0
1 4
1 1
1 4
1 5

一种正确输出为:

1
3 1 3 4

在上述样例中,邀请 1、3、4 号宾客比邀请 1、4、5、6 号宾客更好。根据国王的判定标准,决定更好集合的是编号为 3 的人。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.