QOJ.ac

QOJ

実行時間制限: 1 s メモリ制限: 1024 MB 満点: 100

#6664. 学生们

統計

IOI 大学的学生们生活在一个冷酷的竞争社会中,他们不以名字相称,而是以考试排名相称。大学里有 $N$ 名学生,对于每个 $0 \le i \le N - 1$,编号为 $i$ 的学生在期中考试中排名第 $i + 1$。

为了准备期末考试,学生们自发组成了辅导小组。每个辅导小组可以用两个整数 $0 \le L \le R \le N - 1$ 来表示,这意味着除了编号在 $L$ 到 $R$ 之间的学生外,其余所有学生都属于该小组。

一天早上,IOI 大学的全体学生都收到了一封邮件,称“至少存在一个辅导小组”。我们将这一天称为第 1 天。从第 $d \ge 1$ 天的晚上开始,将发生以下情况:

  • 如果某位学生在第 $d$ 天早上之后推断出存在一个将自己排除在外的辅导小组,该学生会感到不公,并在第 $d$ 天晚上结束前提交申诉。一旦收到申诉,所有辅导小组的活动将在第 $d + 1$ 天早上到来前终止。
  • 如果没有任何学生推断出存在一个将自己排除在外的辅导小组,则不会收到申诉,辅导小组的活动将在第 $d + 1$ 天早上继续进行。通过这一点,所有学生都会获得一个共同信息:“没有人在这第 $d$ 天提交申诉”。

除此之外,学生们不会以任何方式分享信息。也就是说,他们只能知道自己所属的辅导小组、每个小组的成员以及是否有人提交了申诉。学生总是会根据自己掌握的信息推断出所有可能的命题,并且不会根据自己掌握的信息推断出可能错误的命题。

你是 IOI 大学的外部人士,与所有学生关系密切,了解所有的辅导小组及其成员。给定关于 $M$ 个辅导小组的所有信息,请编写一个程序,求出提交申诉的日期 $k$,以及在第 $k$ 天提交申诉的学生编号。如果永远不会收到申诉,则返回 $-1$。

请注意,关于小组数量 $M$、每个小组的成员、整个问题及子任务的限制、所有小组都是排除特定范围编号学生的形式等所有信息,只有作为外部人士的你才知道,每个学生对此一无所知。

函数列表及定义

你需要实现以下函数:

pair<int, vector<int> > complaint(int N, vector<int> L, vector<int> R)
  • $L, R$: 大小为 $M$ 的整数数组。对于所有 $0 \le i \le M - 1$,第 $i$ 个辅导小组仅由编号小于 $L[i]$ 或大于 $R[i]$ 的学生组成。
  • 该函数应返回一个由整数 $k$ 和大小不超过 $N$ 的整数数组 $V$ 组成的序对。$k$ 是提交申诉的日期,$V$ 应该包含在第 $k$ 天提交申诉的学生编号,并按升序排列。如果永远不会收到申诉,则 $k$ 应为 $-1$,$V$ 应为空数组。

提交的源代码中不得执行任何输入输出函数。

数据范围

  • $1 \le N \le 250\,000$
  • $1 \le M \le 250\,000$
  • 对于所有 $0 \le i \le M - 1$,满足 $0 \le L[i] \le R[i] \le N - 1$

子任务

  1. (12分) $N, M \le 10$
  2. (6分) 对于所有 $0 \le i \le M - 1$,满足 $L[i] = R[i]$。
  3. (15分) $N, M \le 2\,500$
  4. (10分) 对于所有 $0 \le i, j \le M - 1$,区间 $[L[i], R[i]]$ 和 $[L[j], R[j]]$ 要么不相交,要么相互包含。即如果 $L[i] < L[j]$,则满足 $R[i] < L[j]$ 或 $R[j] \le R[i]$。
  5. (18分) 对于所有 $0 \le i \le M - 2$,满足 $L[i] < L[i + 1]$ 且 $R[i] < R[i + 1]$。
  6. (39分) 无额外限制。

样例

样例 1

考虑 $N = 6, M = 3, L = [1, 2, 3], R = [4, 5, 3]$ 的情况。

评测程序调用如下:

complaint(6, [1, 2, 3], [4, 5, 3])

由于 3 号学生被所有辅导小组排除在外,他在第一天就提交了申诉。由于其他学生在第一天没有提交申诉,函数应返回 $k = 1$ 和 $V = [3]$ 组成的序对 $(1, [3])$。

样例 2

考虑 $N = 10, M = 4, L = [1, 4, 8, 2], R = [4, 7, 9, 6]$ 的情况。

评测程序调用如下:

complaint(10, [1, 4, 8, 2], [4, 7, 9, 6])

函数应返回 $k = 2$ 和 $V = [4, 8, 9]$ 组成的序对 $(2, [4, 8, 9])$。

样例 3

考虑 $N = 5, M = 1, L = [0], R = [4]$ 的情况。

评测程序调用如下:

complaint(5, [0], [4])

该辅导小组不包含任何学生。(是谁创建了这样的辅导小组?)

函数应返回 $k = 1$ 和 $V = [0, 1, 2, 3, 4]$ 组成的序对 $(1, [0, 1, 2, 3, 4])$。

Sample grader

Sample grader 按以下格式接收输入:

  • 第 1 行:$N \ M$
  • 第 $2 + i$ 行 ($0 \le i \le M - 1$):$L[i] \ R[i]$

Sample grader 输出以下内容:

  • 第 1 行:complaint 函数返回的值 $k$
  • 第 2 行:complaint 函数返回的值 $V$ 的元素,以空格分隔。

请注意,Sample grader 可能与实际评测中使用的评测程序不同。

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
EditorialOpen Official EditorialQingyu- Download

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.