Project Manager

题目描述

There are $ n $ employees at Bersoft company, numbered from $ 1 $ to $ n $ . Each employee works on some days of the week and rests on the other days. You are given the lists of working days of the week for each employee. There are regular days and holidays. On regular days, only those employees work that have the current day of the week on their list. On holidays, no one works. You are provided with a list of days that are holidays. The days are numbered from $ 1 $ onwards, day $ 1 $ is Monday. The company receives $ k $ project offers they have to complete. The projects are numbered from $ 1 $ to $ k $ in the order of decreasing priority. Each project consists of multiple parts, where the $ i $ -th part must be completed by the $ a_i $ -th employee. The parts must be completed in order (i. e. the $ (i+1) $ -st part can only be started when the $ i $ -th part is completed). Each part takes the corresponding employee a day to complete. The projects can be worked on simultaneously. However, one employee can complete a part of only one project during a single day. If they have a choice of what project to complete a part on, they always go for the project with the highest priority (the lowest index). For each project, output the day that project will be completed on.

输入输出格式

输入格式

The first line contains three integers $ n, m $ and $ k $ ( $ 1 \le n, m, k \le 2 \cdot 10^5 $ ) — the number of employees, the number of holidays and the number of projects. The $ i $ -th of the next $ n $ lines contains the list of working days of the $ i $ -th employee. First, a single integer $ t $ ( $ 1 \le t \le 7 $ ) — the number of working days. Then $ t $ days of the week in the increasing order. The possible days are: "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday". The next line contains $ m $ integers $ h_1, h_2, \dots, h_m $ ( $ 1 \le h_1 < h_2 < \dots < h_m \le 10^9 $ ) — the list of holidays. The $ j $ -th of the next $ k $ lines contains a description of the $ j $ -th project. It starts with an integer $ p $ ( $ 1 \le p \le 2 \cdot 10^5 $ ) — the number of parts in the project. Then $ p $ integers $ a_1, a_2, \dots, a_p $ ( $ 1 \le a_x \le n $ ) follow, where $ p_i $ is the index of the employee that must complete the $ i $ -th part. The total number of parts in all projects doesn't exceed $ 2 \cdot 10^5 $ .

输出格式

Print $ k $ integers — the $ j $ -th value should be equal to the day the $ j $ -th project is completed on.

输入输出样例

输入样例 #1

3 5 4
2 Saturday Sunday
2 Tuesday Thursday
4 Monday Wednesday Friday Saturday
4 7 13 14 15
5 1 1 3 3 2
3 2 3 2
5 3 3 3 1 1
8 3 3 3 3 3 3 3 3

输出样例 #1

25 9 27 27

**项目管理**

**题目描述：**
Bersoft公司有 $ n $ 名员工，编号从 $ 1 $ 到 $ n $。每位员工在一周中的某些天工作，其他天休息。你将获得每位员工的工作日列表。有常规日和假日。在常规日，只有那些在他们的工作日列表上的员工会工作。在假日，没有人工作。你将获得一个假日列表。从 $ 1 $ 开始编号，第 $ 1 $ 天是星期一。

公司收到 $ k $ 个项目提议，他们必须完成。项目按优先级递减的顺序从 $ 1 $ 到 $ k $ 编号。

每个项目由多个部分组成，第 $ i $ 个部分必须由第 $ a_i $ 个员工完成。部分必须按顺序完成（即第 $ i+1 $ 个部分只能在完成第 $ i $ 个部分后开始）。每个部分需要相应的员工一天时间来完成。

项目可以同时进行。然而，一个员工在单天内只能完成一个项目的部分。如果他们可以选择完成哪个项目的部分，他们总是选择优先级最高的项目（即索引最小的项目）。

对于每个项目，输出该项目将在哪一天完成。

**输入输出格式：**

**输入格式：**
第一行包含三个整数 $ n, m $ 和 $ k $（$ 1 \le n, m, k \le 2 \cdot 10^5 $）——员工数量、假日数量和项目数量。

接下来的 $ n $ 行中的第 $ i $ 行包含第 $ i $ 位员工的工作日列表。首先是一个整数 $ t $（$ 1 \le t \le 7 $）——工作日数量。然后是 $ t $ 个递增的工作日。可能的天数有："Monday"、"Tuesday"、"Wednesday"、"Thursday"、"Friday"、"Saturday"、"Sunday"。

下一行包含 $ m $ 个整数 $ h_1, h_2, \dots, h_m $（$ 1 \le h_1 < h_2 < \dots < h_m \le 10^9 $）——假日列表。

接下来的 $ k $ 行中的第 $ j $ 行包含第 $ j $ 个项目的描述。以一个整数 $ p $（$ 1 \le p \le 2 \cdot 10^5 $）开始——项目的部分数量。然后是 $ p $ 个整数 $ a_1, a_2, \dots, a_p $（$ 1 \le a_x \le n $），其中 $ p_i $ 是必须完成第 $ i $ 部分的员工的索引。

所有项目的部分总数不超过 $ 2 \cdot 10^5 $。

**输出格式：**
打印 $ k $ 个整数——第 $ j $ 个值应等于第 $ j $ 个项目将在哪一天完成。

**输入输出样例：**

**输入样例 #1:**
```
3 5 4
2 Saturday Sunday
2 Tuesday Thursday
4 Monday Wednesday Friday Saturday
4 7 13 14 15
5 1 1 3 3 2
3 2 3 2
5 3 3 3 1 1
8 3 3 3 3 3 3 3 3
```

**输出样例 #1:**
```
25 9 27 27
```**项目管理** **题目描述：** Bersoft公司有 $ n $ 名员工，编号从 $ 1 $ 到 $ n $。每位员工在一周中的某些天工作，其他天休息。你将获得每位员工的工作日列表。有常规日和假日。在常规日，只有那些在他们的工作日列表上的员工会工作。在假日，没有人工作。你将获得一个假日列表。从 $ 1 $ 开始编号，第 $ 1 $ 天是星期一。 公司收到 $ k $ 个项目提议，他们必须完成。项目按优先级递减的顺序从 $ 1 $ 到 $ k $ 编号。 每个项目由多个部分组成，第 $ i $ 个部分必须由第 $ a_i $ 个员工完成。部分必须按顺序完成（即第 $ i+1 $ 个部分只能在完成第 $ i $ 个部分后开始）。每个部分需要相应的员工一天时间来完成。 项目可以同时进行。然而，一个员工在单天内只能完成一个项目的部分。如果他们可以选择完成哪个项目的部分，他们总是选择优先级最高的项目（即索引最小的项目）。 对于每个项目，输出该项目将在哪一天完成。 **输入输出格式：** **输入格式：** 第一行包含三个整数 $ n, m $ 和 $ k $（$ 1 \le n, m, k \le 2 \cdot 10^5 $）——员工数量、假日数量和项目数量。 接下来的 $ n $ 行中的第 $ i $ 行包含第 $ i $ 位员工的工作日列表。首先是一个整数 $ t $（$ 1 \le t \le 7 $）——工作日数量。然后是 $ t $ 个递增的工作日。可能的天数有："Monday"、"Tuesday"、"Wednesday"、"Thursday"、"Friday"、"Saturday"、"Sunday"。 下一行包含 $ m $ 个整数 $ h_1, h_2, \dots, h_m $（$ 1 \le h_1 < h_2 < \dots < h_m \le 10^9 $）——假日列表。 接下来的 $ k $ 行中的第 $ j $ 行包含第 $ j $ 个项目的描述。以一个整数 $ p $（$ 1 \le p \le 2 \cdot 10^5 $）开始——项目的部分数量。然后是 $ p $ 个整数 $ a_1, a_2, \dots, a_p $（$ 1 \le a_x \le n $），其中 $ p_i $ 是必须完成第 $ i $ 部分的员工的索引。 所有项目的部分总数不超过 $ 2 \cdot 10^5 $。 **输出格式：** 打印 $ k $ 个整数——第 $ j $ 个值应等于第 $ j $ 个项目将在哪一天完成。 **输入输出样例：** **输入样例 #1:** ``` 3 5 4 2 Saturday Sunday 2 Tuesday Thursday 4 Monday Wednesday Friday Saturday 4 7 13 14 15 5 1 1 3 3 2 3 2 3 2 5 3 3 3 1 1 8 3 3 3 3 3 3 3 3 ``` **输出样例 #1:** ``` 25 9 27 27 ```