分数: 100 点
如何提交到AtCoder
- 包括
Azzurro.h和Bordeaux.h,并实现语句中指定的功能。- 不要使用标准输入/输出或文件输入/输出。
问题陈述
Azzurro 和 Bordeaux 两人参观了意大利的一家赌场,决定玩庄家 Chiaro 提议的游戏。
在这个游戏中,信息是使用 N \times N 网格(N = 8))。网格的行编号为 0 to N - 1 从上到下,网格的列编号从 0 to N - 1 从左到右。具有行号的单元格 r 和列号 c 表示为 (r, c).
在这个游戏中,Azzurro 和 Bordeaux 被隔离在不同的房间里。他们会玩 Q 转。的 i第回合(1 \leq i \leq Q) 进行如下。
- Azzurro 从 Chiaro 收到一个整数 N,一个整数 L_i (1 \leq L_i \leq 51),一张卡片,上面有一个字符串 S_i 长度 L_i 组成 '
A' 和 'B' 被写入,并且 N \times N 网格,其单元格全部为白色。 - Azzurro 为每个 N^2 细胞为蓝色或红色。然后他将网格交给 Chiaro。
- Chiaro 在 Azzurro 和 Bordeaux 的视线之外执行以下操作。
- 他从以下选择一条路径 (0, 0) to (N - 1, N - 1) 通过重复向下或向右仅移动到相邻单元格。
- 对于路径上的每个单元格,如果该单元格颜色为蓝色,则他将其重新绘制为红色;如果它是红色的,他就把它重新漆成蓝色。
A 和 B 在一张纸上。如果写入的字符串匹配 S_i,蓝色军团和波尔多获胜。
编写实现 Azzurro 和 Bordeaux 策略的程序 赢得这场比赛。有关此任务的评分,请参阅 评分.
实施细节
您需要提交两个文件。
第一个文件是 Azzurro.cpp。它应该执行蓝衣军团的战略。它应该实现以下功能。该计划应包括 Azzurro.h 使用预处理指令 #include.
-
std::vector<std::vector<int>> Azzurro(int N, int L, std::string S)该函数被调用 Q 次。 i第次调用 (1 \leq i \leq Q) 对应于程序 1., 2.\ i-第轮游戏。- 参数
N是整数 在程序 1.\ 中交给 Azzurro 的卡片上写有 N 写在在程序 1.\ 中交给 Azzurro 的卡片上 i第回合。 - 参数
L是整数 在程序 1.\ 中交给 Azzurro 的卡片上写有 L_i 写在在程序 1.\ 中交给 Azzurro 的卡片上 i第回合。 - 参数
S是字符串 S_i 写在在程序 1.\ 中交给 Azzurro 的卡片上 i第回合。
- 参数
Azzurro,你的程序必须返回一个 N \times N 二维数组 x,其每个元素是 0 or 1。如果不满足这个条件,你的程序被判定为 错误答案 [1].
- If \texttt{x}[\texttt{r}][\texttt{c}] = 0 (0 \leq \texttt{r} \leq N - 1, 0 \leq \texttt{c} \leq N - 1),表明该单元格 (\texttt{r}, \texttt{c}) 为蓝色。
- If \texttt{x}[\texttt{r}][\texttt{c}] = 1 (0 \leq \texttt{r} \leq N - 1, 0 \leq \texttt{c} \leq N - 1),表明该单元格 (\texttt{r}, \texttt{c}) 为红色。
第二个文件是 Bordeaux.cpp。它应该实施波尔多的战略。它应该实现以下功能。该计划应包括 Bordeaux.h 使用预处理指令 #include.
-
std::string Bordeaux(int N, int L, std::vector<std::vector<int>> T)每次 Azzurro 完成网格绘制时都会调用此函数。 总共 Q 次。 i第次调用 (1 \leq i \leq Q) 对应于程序 4., 5.\ i-第轮游戏。- 参数
N是整数 在程序 1.\ 中交给 Azzurro 的卡片上写有 N 写在在程序 4.\ 中给波尔多的卡上 i第回合。 - 参数
L是整数 在程序 1.\ 中交给 Azzurro 的卡片上写有 L_i 写在在程序 4.\ 中给波尔多的卡上 i第回合。 - 参数
T是 N \times N 二维数组,对应于程序 4.\ 中给出的 Bordeaux 的单元格网格 i第回合。细胞的颜色 (\texttt{r}, \texttt{c}) (0 \leq \texttt{r} \leq N - 1,0 \leq \texttt{c} \leq N - 1) 为蓝色,如果 \texttt{T[a][b]} = 0,如果 \texttt{T[a][b]} = 1.
- 参数
Bordeaux,您的程序必须返回一个字符串 s 长度 L_i 组成 'A' 和 'B'。如果不满足这个条件,你的程序被判定为 错误答案 [2].
重要通知
- 您的程序可以实现其他内部使用的函数,或使用全局变量。提交的文件将使用评分器进行编译,并成为单个可执行文件。所有全局变量和内部函数都应在未命名的命名空间中声明,以避免与其他文件冲突。分级时将分Azzurro和Bordeaux两个流程执行。 Azzurro进程和Bordeaux进程不能共享全局变量。
- 您的程序不得使用标准输入和标准输出。您的程序不得通过任何方法与其他文件通信。但是,您的程序可能会将调试信息输出到标准错误。
编译和测试运行
您可以从竞赛网页下载存档文件,其中包含用于测试您的程序的示例评分器。存档文件还包含程序的示例源文件。
示例评分器是文件 grader.cpp。为了测试您的程序,请输入 grader.cpp,Azzurro.cpp,Bordeaux.cpp,Azzurro.h,Bordeaux.h 在同一目录中,并运行以下命令来编译程序。
g++ -std=gnu++20 -O2 -o grader grader.cpp Azzurro.cpp Bordeaux.cpp
相反,你可以运行 compile.sh 包含在存档文件中。在这种情况下,运行以下命令来编译您的程序。
./compile.sh
编译成功后,生成可执行文件
生成 grader 。
请注意,实际评分器与示例评分器不同。示例分级器将作为单个进程执行,该进程将从标准输入读取输入数据并将结果写入标准输出。
在实际的评审评分中, Chiaro选择的路径是预先固定的。也就是说,Chiaro选择的路径是在函数之前确定的 Azzurro 和 Bordeaux 在您提交的程序中被调用。
样本分级机的输入
示例分级器从标准输入读取以下数据。
Q N L_1 S_1 R_1 L_2 S_2 R_2 \vdots L_Q S_Q R_Q
在这里, R_i (1 \leq i \leq Q) 是一个长度的字符串 2(N - 1) 完全由 N - 1 出现 'D' 和 N - 1 出现 'R'。该字符串代表 Chiaro 在 i第回合,从 (0, 0) 并达到 (N - 1, N - 1) 通过重复向下或向右仅移动到相邻单元格。具体来说,从 (0, 0),对于每个 j = 1, 2, \cdots, 2(N - 1),如果 j- 第一个字符 R_i 是 'D',移动到下面的相邻单元格;如果是'R',移动到右侧相邻的单元格。重复此过程可达到 (N - 1, N - 1).
样本分级机的输出
示例分级器将以下信息输出到标准输出(为了清楚起见,引用)。
- 如果你的程序被判断为正确,它会写入以下值 L^{*} 作为“
Accepted: 26“。对于价值 L^{*},请参阅评分。 - 如果您的程序被判断为任何类型的错误答案,则示例评分器将其类型写为“
Wrong Answer [1]".
如果您的程序满足多种类型的错误答案的条件,则示例评分器仅报告其中一种。当满足错误答案的条件之一时,样本评分者可以终止执行。
约束
所有输入数据满足以下条件。
- 1 \leq Q \leq 30\,000.
- N = 8.
- 1 \leq L_i \leq 51 (1 \leq i \leq Q).
- Q, L_i (1 \leq i \leq Q) 是整数。
- S_i (1 \leq i \leq Q) 是一个长度的字符串 L_i 组成 '
A' 和 'B'. - R_i (1 \leq i \leq Q) 是一个长度的字符串 2(N - 1) 完全由 N - 1 出现 '
D' 和 N - 1 出现 'R'.
评分
如果你的程序被判断为任何类型 错误答案 [1] or 错误答案 [2] (请参阅实现详细信息)、超出时间限制、超出内存限制或运行时错误,在任何测试用例中,您的分数为 0 点。
否则,让 L^{*} 是此任务的所有测试用例的以下值中的最小值。您的分数计算如下表所示。
- 的最大值 L 使得 Azzurro 和 Bordeaux 赢得所有令人满意的回合 L_i \leq L。然而,如果他们赢得了测试用例中的所有回合,我们设置 L = 51.

通讯示例
以下是示例评分器和相应函数调用的示例输入。
示例输入 1
2 2 1 B RD 3 ABB DR

该示例输入包括 Q \ (= 2) 轮流,并且在每一轮中 使用 N \times N 网格(N = 2)。在此示例中,第一轮进行如下。
- 蓝色 (0, 1) 和 (1, 0) 蓝色,和 (0, 0) 和 (1, 1) 红色。然后他将网格交给 Chiaro。
- Chiaro 在 Azzurro 和 Bordeaux 的视线之外执行以下操作。
- 他选择了路径 (0, 0) \rightarrow (0, 1) \rightarrow (1, 1) 作为路径 (0, 0) to (N - 1, N - 1) 通过重复向下或向右仅移动到相邻单元格。
- 对于三个单元格 (0, 0), (0, 1), (1, 1) 在这条路上,他改变了它们的颜色。结果,颜色 (0, 0), (0, 1), (1, 1) 分别变为蓝色、红色和蓝色。
B”在纸上。
第二回合进行如下。
- Azzurro 将所有单元格设置为蓝色。然后他将网格交给 Chiaro。
- Chiaro 在 Azzurro 和 Bordeaux 的视线之外执行以下操作。
- 他选择了路径 (0, 0) \rightarrow (1, 0) \rightarrow (1, 1) 作为路径 (0, 0) to (N - 1, N - 1) 通过重复向下或向右仅移动到相邻单元格。
- 对于三个单元格 (0, 0), (1, 0), (1, 1) 在这条路上,他改变了它们的颜色。结果,颜色 (0, 0), (1, 0), (1, 1) 全部变成红色。
ABB”在纸上。
请注意,此示例输入 不满足 问题的制约。该文件 sample-01-in.txt,可以从竞赛网站下载,对应于示例输入 1。该文件 sample-02-in.txt是满足约束的示例输入,可以从竞赛网站下载。