QOJ.ac

QOJ

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

#7801. 最先解决,最后编码

統計

在 ICPC 中,团队合作至关重要。这就是为什么团队中的每个人都有明确的分工:Sol 是解题者,可以解决题集中的任何问题;Codie 是编码者,可以实现 Sol 给出的任何解决方案;而你……是维系整个团队的纽带。Sol 和 Codie 对他们解决/编码问题的顺序非常挑剔,你的工作就是满足他们的偏好。

即将到来的比赛中有 $n$ 道题目,你知道每道题的主题:贪心、几何、图论等。为简化起见,我们用 $1$ 到 $n$ 之间的整数来表示每个主题。这些整数不必是唯一的,也就是说,比赛中的多道题目可以具有相同的主题。

Sol 希望按照特定的主题顺序解决问题:首先是主题为 $a_1$ 的题目,然后是主题为 $a_2$ 的题目,……,最后是主题为 $a_n$ 的题目。Codie 也有一个偏好列表:$b_1, b_2, \dots, b_n$,他只愿意按照这个主题顺序对题目进行编码。

你在比赛中的工作是从 Sol 那里获取解决方案,并按正确的顺序交给 Codie。由于你们团队只有一张桌子可用,你没有足够的空间整齐地排列所有解决方案。因此,你设计了以下工作流程:你向 Sol 请求解决方案(他会按 $a_1, a_2, \dots, a_n$ 的顺序交给你),将它们存储在桌子上的一个栈中,然后交给 Codie 进行编码(按 $b_1, b_2, \dots, b_n$ 的顺序)。

更正式地说,在比赛的任何时刻,你(最多)可以执行以下两种操作之一: 如果还有未解决的题目,向 Sol 请求另一个解决方案,并将其放在你的解决方案栈的顶部。此操作用字符 ‘S’ 表示。 如果你的栈不为空,从栈顶取出一份解决方案并交给 Codie 实现。此操作用字符 ‘C’ 表示。

对于给定的 Sol 和 Codie 的偏好列表,请找到一个操作序列,确保所有问题都能按正确的顺序解决和编码。假设所有解题和编码的时间都可以忽略不计——毕竟,管理解决方案表是一项更艰巨、更重要的工作。

输入格式

第一行包含一个整数 $n$,表示比赛中的题目数量 ($1 \le n \le 100$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$,表示 Sol 偏好的主题顺序 ($1 \le a_i \le n$)。 第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$,表示 Codie 偏好的主题顺序 ($1 \le b_i \le n$)。 给定的列表作为多重集是相等的:每个整数在 $A$ 和 $B$ 中出现的次数相同。

输出格式

如果任务无法完成,输出 “NO”。否则,第一行输出 “YES”,第二行输出操作序列:一个由 $2n$ 个字符 ‘S’ 或 ‘C’(各 $n$ 个)组成的字符串,按顺序描述你的操作。

如果所有 $n$ 道题都已经解决,你不得再向 Sol 请求解决方案;如果给 Codie 的解决方案主题错误,也是不允许的。如果存在多种答案,输出其中任意一个即可。

样例

样例输入 1

4
4 1 2 2
1 2 4 2

样例输出 1

YES
SSCSCCSC

样例输入 2

3
2 3 1
1 2 3

样例输出 2

NO

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.