QOJ.ac

QOJ

時間限制: 3 s 記憶體限制: 512 MB 總分: 100

#3387. 特殊服务

统计

你被指派为一家特殊服务公司制作一个预订系统。这家公司提供各种服务,但你被告知不要问任何问题。在你之前已经有一些开发人员尝试过制作这个系统,但遗憾的是他们都下落不明,所以你无法向他们寻求任何帮助。

系统会逐个接收预订(和取消)请求,并必须立即接受或拒绝该预订。所有预订的持续时间均为一整天,而你所负责的系统部分只需要跟踪单日的情况。

公司拥有若干名员工,每名员工拥有一项或多项资格。每个预订除了有一个给定的数字标识符外,还需要一定数量的人员(员工),且每人需具备特定的资格。在这一整天中,一个人最多只能满足一个预订中的一个需求。主管以马里奥为例:虽然马里奥既可以是水管工也可以是刺客,但在同一天内,他只能为(该公司)的一个预订完成其中一项工作。

当且仅当满足以下条件时,预订才会被接受: 没有具有该特定标识符的活跃预订,并且 可以使用现有员工,满足当前所有活跃预订以及新预订的需求。

当且仅当满足以下条件时,取消请求才会被接受: * 存在一个具有该特定标识符的活跃预订。

输入格式

第一行包含 $T$,即测试用例的数量。每个测试用例的第一行包含数字 $N$ 和 $B$,分别表示该测试用例中的员工数量和预订/取消请求数量。

接下来有 $N$ 行,每行描述一名员工。每行包含一个数字 $c$,后跟 $c$ 个以空格分隔的字符串,表示该员工拥有的每项资格的名称。

随后有 $B$ 行,每行包含一个预订或取消请求。预订以单词 book 开头,后跟该预订的数字标识符 $I$,接着是数字 $d$,最后是 $d$ 个以空格分隔的字符串,表示该预订的所有资格需求。取消请求由单词 cancel 后跟一个数字组成,该数字指代要取消的预订的标识符 $I$。

输出格式

对于每个预订/取消请求,输出一行。如果预订/取消被接受,则该行应包含单词 Accepted,否则输出 Rejected

数据范围

  • $0 < T \le 50$
  • $1 \le N \le 200$
  • $1 \le B \le 1000$
  • $1 \le c \le 16$
  • $0 \le d \le 16$
  • $0 \le I \le 1000$
  • 资格名称长度最多为 10 个字符。所有员工共享的资格种类不超过 100 种。
  • 活跃预订是指已被接受且尚未成功取消的预订。
  • 可以进行不预留任何人员的预订。这些预订将由公司经理处理,你无需过问。
  • 这是一个 I/O 密集型问题。对于 Java 程序员,这意味着你应该使用 BufferedReader 进行输入读取(而不是 Scanner)。

样例

输入 1

2
1 1
1 slacker
book 6 1 worker
3 6
2 plumber nurse
2 nurse assassin
2 assassin plumber
cancel 1
book 1 2 plumber assassin
book 123 1 nurse
book 4 3 assassin nurse plumber
cancel 1
book 4 2 nurse assassin

输出 1

Rejected
Rejected
Accepted
Accepted
Rejected
Accepted
Accepted

主管以马里奥为例:虽然马里奥既可以是水管工也可以是刺客,但在同一天内,他只能为(该公司)的一个预订完成其中一项工作。

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.