33OJ
登录 注册

#P15942. [JOI Final 2026] 赌场 / Casino

    ID: 20123 远端评测题 5000ms 1024MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>交互题Special JudgeJOI(日本)2026通信题

[JOI Final 2026] 赌场 / Casino

背景

评测说明(请仔细阅读)

  1. 不要 #include{\texttt{\#include}}。
  2. 请使用 C++20\red{\texttt{C++20}}。

题目描述

这是一道通信题。本题中,交互库是非自适应的。

Azzurro 和 Bordeaux 是一对在意大利游览赌场的伴侣,他们决定玩一个由荷官 Chiaro 提议的游戏。

在这个游戏中,信息通过一个 N×NN \times N 的网格 (N=8N = 8) 进行传递。网格的行从上到下编号为 00 到 N−1N-1,列从左到右编号为 00 到 N−1N-1。 行号为 rr、列号为 cc 的单元格记作 (r,c)(r, c)。

在这个游戏中,Azzurro 和 Bordeaux 被隔离在不同的房间里。他们将进行 QQ 轮游戏。第 ii 轮 (1≤i≤Q1 \leq i \leq Q) 的过程如下。

  1. Azzurro 从 Chiaro 那里收到一个整数 NN、一个整数 LiL_i (1≤Li≤511 \leq L_i \leq 51)、一张写有长度为 LiL_i 且由 'A' 和 'B' 组成的字符串 SiS_i 的卡片,以及一个单元格全是白色的 N×NN \times N 网格。
  2. Azzurro 将 N2N^2 个单元格中的每一个涂成蓝色或红色。然后他将网格交给 Chiaro。
  3. Chiaro 在 Azzurro 和 Bordeaux 都看不见的情况下执行以下操作。 (a) 他选择一条从 (0,0)(0,0) 到 (N−1,N−1)(N-1, N-1) 的路径,移动方式仅限重复向相邻的下方或右方单元格移动。 (b) 对于路径上的每个单元格,如果该单元格颜色为蓝色,他将其重涂为红色;如果颜色为红色,他将其重涂为蓝色。
  4. Bordeaux 从 Chiaro 那里收到一张写有整数 NN 和 LiL_i 的卡片以及该网格。
  5. Bordeaux 在一张纸上写下一个长度为 LiL_i 且由 A 和 B 组成的字符串。如果写下的字符串与 SiS_i 匹配,则 Azzurro 和 Bordeaux 获胜。

编写程序实现 Azzurro 和 Bordeaux 在此游戏中获胜的策略。关于此任务的评分,请参阅“评分”。

实现细节

你需要提交两个文件。 第一个文件是 Azzurro.cpp\texttt{Azzurro.cpp}。它应该实现 Azzurro 的策略。它应该实现以下函数。程序应使用预处理指令 #include 包含 Azzurro.h\texttt{Azzurro.h}。

std::vector<std::vector<int>> Azzurro(int N, int L, std::string S)

该函数被调用 QQ 次。第 ii 次调用 (1≤i≤Q1 \leq i \leq Q) 对应于游戏第 ii 轮的过程 1 和 2。

  • 参数 N\texttt{N} 是第 ii 轮过程 1 中交给 Azzurro 的卡片上写的整数 NN。
  • 参数 L\texttt{L} 是第 ii 轮过程 1 中交给 Azzurro 的卡片上写的整数 LiL_i。
  • 参数 S\texttt{S} 是第 ii 轮过程 1 中交给 Azzurro 的卡片上写的字符串 SiS_i。

对于每次 Azzurro 函数调用,你的程序必须返回一个 N×NN \times N 的二维数组 x\texttt{x},其每个元素均为 00 或 11。如果不满足此条件,你的程序将被判定为 Wrong Answer [1]。

  • 如果 x[r][c]=0\texttt{x[r][c]}=0 (0≤r≤N−1,0≤c≤N−10 \leq r \leq N-1, 0 \leq c \leq N-1),表示单元格 (r,c)(r, c) 涂成蓝色。
  • 如果 x[r][c]=1\texttt{x[r][c]} = 1 (0≤r≤N−1,0≤c≤N−10 \leq r \leq N-1, 0 \leq c \leq N-1),表示单元格 (r,c)(r, c) 涂成红色。

第二个文件是 Bordeaux.cpp\texttt{Bordeaux.cpp}。它应该实现 Bordeaux 的策略。它应该实现以下函数。程序应使用预处理指令 #include 包含 Bordeaux.h\texttt{Bordeaux.h}。

std::string Bordeaux(int N, int L, std::vector<std::vector<int>> T)

该函数在 Azzurro 每次完成网格涂色后被调用。该函数总共被调用 QQ 次。第 ii 次调用 (1≤i≤Q1 \leq i \leq Q) 对应于游戏第 ii 轮的过程 4 和 5。

  • 参数 N\texttt{N} 是第 ii 轮过程 4 中交给 Bordeaux 的卡片上写的整数 NN。
  • 参数 L\texttt{L} 是第 ii 轮过程 4 中交给 Bordeaux 的卡片上写的整数 LiL_i。
  • 参数 T\texttt{T} 是对应于第 ii 轮过程 4 中交给 Bordeaux 的网格的 N×NN \times N 二维数组。如果 T[a][b]=0\texttt{T[a][b]} = 0,则单元格 (r,c)(r, c) (0≤r≤N−1,0≤c≤N−10 \leq r \leq N-1, 0 \leq c \leq N-1) 的颜色为蓝色;如果 T[a][b]=1\texttt{T[a][b]} = 1,则为红色。

对于每次 Bordeaux 函数调用,你的程序必须返回一个长度为 LiL_i 且由 'A\texttt{A}' 和 'B\texttt{B}' 组成的字符串 s。如果不满足此条件,你的程序将被判定为 Wrong Answer [2]。

重要注意事项

  • 你的程序可以实现其他用于内部使用的函数,或使用全局变量。提交的文件将与评测程序(grader)一同编译,并生成一个单一的可执行文件。所有全局变量和内部函数应声明在匿名命名空间中,以避免与其他文件冲突。在评测时,它将作为 Azzurro 和 Bordeaux 两个进程执行。Azzurro 进程和 Bordeaux 进程不能共享全局变量。
  • 你的程序不得使用标准输入和标准输出。你的程序不得通过任何方法与其他文件通信。但是,你的程序可以向标准错误输出调试信息。

编译与测试运行

你可以从竞赛网页下载一个压缩文件,其中包含用于测试程序的示例评测程序。该压缩文件还包含你程序的示例源文件。

示例评测程序是文件 grader.cpp\texttt{grader.cpp}。为了测试你的程序,请将 grader.cpp\texttt{grader.cpp}、Azzurro.cpp\texttt{Azzurro.cpp}、Bordeaux.cpp\texttt{Bordeaux.cpp}、Azzurro.h\texttt{Azzurro.h}、Bordeaux.h\texttt{Bordeaux.h} 放在同一个目录下,并运行以下命令来编译你的程序。

g++ -std=gnu++20 -O2 -o grader grader.cpp Azzurro.cpp Bordeaux.cpp

或者,你可以运行压缩文件中包含的 compile.sh\texttt{compile.sh}。在这种情况下,运行以下命令来编译你的程序。

./compile.sh

编译成功后,将生成可执行文件 grader。

注意,实际的评测程序与示例评测程序不同。示例评测程序将作为单个进程执行,它将从标准输入读取输入数据并将结果写入标准输出。

在实际的评测程序中,Chiaro 选择的路径是提前固定的。也就是说,在调用你提交的程序中的 Azzurro\texttt{Azzurro} 和 Bordeaux\texttt{Bordeaux} 函数之前,Chiaro 选择的路径就已经确定了。

输入格式

示例评测程序从标准输入读取以下数据。

QQ NN
L1L_1
S1S_1
R1R_1
L2L_2
S2S_2
R2R_2
⋮\vdots
LQL_Q
SQS_Q
RQR_Q

这里,RiR_i (1≤i≤Q1 \leq i \leq Q) 是一个长度为 2(N−1)2(N-1) 的字符串,恰好包含 N−1N-1 个 'D\texttt{D}' 和 N−1N-1 个 'R\texttt{R}'。该字符串表示 Chiaro 在第 ii 轮中选择的路径,该路径从 (0,0)(0,0) 开始,通过重复向相邻的下方或右方单元格移动到达 (N−1,N−1)(N-1,N-1)。具体来说,从 (0,0)(0,0) 开始,对于每个 j=1,2,⋯ ,2(N−1)j=1,2,\cdots,2(N-1),如果 RiR_i 的第 jj 个字符是 'D\texttt{D}',则向下方相邻单元格移动;如果是 'R\texttt{R}',则向右方相邻单元格移动。重复此过程最终到达 (N−1,N−1)(N-1,N-1)。

输出格式

示例评测程序将以下信息输出到标准输出(引号为了清晰起见)。

  • 如果你的程序被判定为正确,它会写出 L∗L^* 的值,例如 “Accepted: 26\texttt{Accepted: 26}”。关于 L∗L^* 的值,请参阅“评分”。
  • 如果你的程序被判定为任何类型的 Wrong Answer,示例评测程序会将其类型写为 “Wrong Answer [1]”。

如果你的程序满足多种类型的 Wrong Answer 条件,示例评测程序仅报告其中一种。当满足其中一个错误答案条件时,示例评测程序可能会终止执行。

提示

样例交互

以下是示例评测程序的样例输入及对应的函数调用。

输入

2 2
1
B
RD
3
ABB
DR

样例函数调用

函数调用 返回值
Azzurro(2, 1, "B") \texttt{Azzurro(2,\,1,\,"B") } [[1, 0], [0, 1]]\texttt{[[1,\,0],\,[0,\,1]]}
Bordeaux(2, 1, [[0, 1], [0, 0]])\texttt{Bordeaux(2,\,1,\,[[0,\,1],\,[0,\,0]])} "B"\texttt{"B"}
Azzurro(2, 3, "ABB")\texttt{Azzurro(2,\,3,\,"ABB")} [[0, 0], [0, 0]]\texttt{[[0,\,0],\,[0,\,0]]}
Bordeaux(2, 3, [[1, 0], [1, 1]])\texttt{Bordeaux(2,\,3,\,[[1,\,0],\,[1,\,1]])} "ABB"\texttt{"ABB"}

该样例输入包含 Q(=2)Q(=2) 轮,每轮使用一个 N×NN \times N 的网格 (N=2N = 2)。在这个例子中,第一轮过程如下。

  1. Azzurro 将 (00,11) 和 (11,00) 涂成蓝色,将 (00,00) 和 (11,11) 涂成红色。然后他将网格交给 Chiaro。

  2. Chiaro 在 Azzurro 和 Bordeaux 看不见的情况下执行以下操作。

    (a) 他选择路径 (00,00) →\to (00,11) →\to (11,11) 作为从 (00,00) 到 (N−1N - 1,N−1N - 1) 的路径,移动方式仅限重复向相邻的下方或右方单元格移动。

    (b) 对于这条路径上的三个单元格 (00,00), (00,11), (11,11),他改变它们的颜色。结果,(00,00), (00,11), (11,11) 的颜色分别变为蓝色、红色和蓝色。

  3. Bordeaux 可以通过在纸上写下 "B" 来赢得本轮。

第二轮过程如下。

  1. Azzurro 将所有单元格涂成蓝色。然后他将网格交给 Chiaro。

  2. Chiaro 在 Azzurro 和 Bordeaux 看不见的情况下执行以下操作。

    (a) 他选择路径 (00,00) →\to (11,00) →\to (11,11) 作为从 (00,00) 到 (N−1N - 1,N−1N - 1) 的路径,移动方式仅限重复向相邻的下方或右方单元格移动。

    (b) 对于这条路径上的三个单元格 (00,00), (11,00), (11,11),他改变它们的颜色。结果,(00,00), (11,00), (11,11) 的颜色都变为红色。

  3. Bordeaux 可以通过在纸上写下 "ABB" 来赢得本轮。

注意,此样例输入不满足问题的限制条件。可以从竞赛网站下载的文件 sample-01-in.txt\texttt{sample-01-in.txt} 对应于样例输入 1。从竞赛网站下载的文件 sample-02-in.txt\texttt{sample-02-in.txt} 是一个满足限制条件的样例输入。

数据范围

所有输入数据满足以下条件。

  • 1≤Q≤300001 \leq Q \leq 30000。
  • N=8N=8。
  • 1≤Li≤511 \leq L_i \leq 51 (1≤i≤Q1 \leq i \leq Q)。
  • Q,LiQ, L_i (1≤i≤Q1 \leq i \leq Q) 均为整数。
  • SiS_i (1≤i≤Q1 \leq i \leq Q) 是长度为 LiL_i 且由 'A\texttt{A}' 和 'B\texttt{B}' 组成的字符串。
  • RiR_i (1≤i≤Q1 \leq i \leq Q) 是长度为 2(N−1)2(N-1) 的字符串,恰好包含 N−1N-1 个 'D\texttt{D}' 和 N−1N-1 个 'R\texttt{R}'。

评分

如果你的程序在任何测试用例中被判定为任何类型的 Wrong Answer [1] 或 Wrong Answer [2](见实现细节)、超过时间限制、超过内存限制或运行错误,你的分数为 00 分。

否则,设 L∗L^* 为该任务所有测试用例中以下值的最小值。你的分数按以下表格计算。

  • 使得 Azzurro 和 Bordeaux 在所有满足 Li≤LL_i \leq L 的轮次中均获胜的最大 LL 值。但是,如果他们在测试用例中的所有轮次均获胜,我们令 L=51L = 51。
L∗L^* 的值 你的分数
1≤L∗≤281 \leq L^* \leq 28 2L∗2L^* 分
29≤L∗≤3929 \leq L^* \leq 39 L∗+28L^* + 28 分
40≤L∗≤5040 \leq L^* \leq 50 67+3(L∗−40)67 + 3(L^* - 40) 分
L∗=51L^* = 51 100100 分