33OJ
登录 注册

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

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

[JOI Final 2026] 赌场 / Casino

Problem Description

Azzurro and Bordeaux, a pair visiting a casino in Italy, decided to play a game proposed by the dealer Chiaro.

In this game, information is transmitted using an N×NN \times N grid (N=8N = 8). The rows of the grid are numbered from 00 to N−1N-1 from top to bottom, and the columns of the grid are numbered from 00 to N−1N-1 from left to right. A cell with row number rr and column number cc is denoted by (r,c)(r, c).

In this game, Azzurro and Bordeaux are isolated in separate rooms. They will play QQ turns. The ii-th turn (1≤i≤Q1 \leq i \leq Q) proceeds as follows.

  1. Azzurro receives from Chiaro an integer NN, an integer LiL_i (1≤Li≤511 \leq L_i \leq 51), a card on which a string SiS_i of length LiL_i consisting of 'A' and 'B' is written, and an N×NN \times N grid whose cells are all colored white.
  2. Azzurro colors each of the N2N^2 cells either blue or red. He then hands the grid to Chiaro.
  3. Chiaro performs the following operations out of sight of both Azzurro and Bordeaux. (a) He selects one path from (0,0)(0,0) to (N−1,N−1)(N-1, N-1) by repeatedly moving only to an adjacent cell either down or to the right. (b) For every cell on the path, if the cell is colored blue, he repaints it red; if it is colored red, he repaints it blue.
  4. Bordeaux receives from Chiaro a card with integers NN and LiL_i written on it, along with the grid.
  5. Bordeaux writes a string of length LiL_i consisting of A and B on a sheet of paper. If the written string matches SiS_i, Azzurro and Bordeaux win.

Write programs which implement the strategies of Azzurro and Bordeaux to win this game. For the grading of this task, see Grading.

Implementation Details

You need to submit two files. The first file is Azzurro.cpp\texttt{Azzurro.cpp}. It should implement Azzurro’s strategy. It should implement the following functions. The program should include Azzurro.h\texttt{Azzurro.h} using the preprocessing directive #include.

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

This function is called QQ times. The ii-th call (1≤i≤Q1 \leq i \leq Q) corresponds to the procedures 1., 2. of the ii-th turn of the game.

  • The parameter N\texttt{N} is the integer NN written on the card given to Azzurro in the procedure 1. of the ii-th turn.
  • The parameter L\texttt{L} is the integer LiL_i written on the card given to Azzurro in the procedure 1. of the ii-th turn.
  • The parameter S\texttt{S} is the string SiS_i written on the card given to Azzurro in the procedure 1. of the ii-th turn.

For each call to the function Azzurro, your program must return an N×NN \times N two-dimensional array x\texttt{x}, each of whose elements is either 00 or 11. If this condition is not satisfied, your program is judged as Wrong Answer [1]. o If x[r][c]=0\texttt{x[r][c]}=0 (0≤r≤N−10 \leq r \leq N-1, 0≤c≤N−10 \leq c \leq N-1), it indicates that the cell (r,c)(r, c) is colored blue. o If x[r][c]=1\texttt{x[r][c]} = 1 (0≤r≤N−10 \leq r \leq N-1, 0≤c≤N−10 \leq c \leq N-1), it indicates that the cell (r,c)(r, c) is colored red.

The second file is Bordeaux.cpp\texttt{Bordeaux.cpp}. It should implement Bordeaux’s strategy. It should implement the following function. The program should include Bordeaux.h\texttt{Bordeaux.h} using the preprocessing directive #include.

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

This function is called every time when Azzurro finishes painting the grid. This function is called QQ times in total. The ii-th call (1≤i≤Q1 \leq i \leq Q) corresponds to the procedures 4., 5. of the ii-th turn of the game.

  • The parameter N\texttt{N} is the integer NN written on the card given to Bordeaux in the procedure 4. of the ii-th turn.
  • The parameter L\texttt{L} is the integer LiL_i written on the card given to Bordeaux in the procedure 4. of the ii-th turn.
  • The parameter T\texttt{T} is the N×NN \times N two-dimensional array corresponding to the grid of cells given to Bordeaux in the procedure 4. of the ii-th turn. The color of the cell (r,c)(r, c) (0≤r≤N−10 \leq r \leq N-1, 0≤c≤N−10 \leq c \leq N-1) is blue if T[a][b]=0\texttt{T[a][b]} = 0, and red if T[a][b]=1\texttt{T[a][b]} = 1.

For each call to the function Bordeaux, your program must return a string s of length LiL_i consisting of 'A\texttt{A}' and 'B\texttt{B}'. If this condition is not satisfied, your program is judged as Wrong Answer [2].

Important Notices

  • Your program can implement other functions for internal use, or use global variables. Submitted files will be compiled with the grader, and become a single executable file. All global variables and internal functions should be declared in an unnamed namespace to avoid conflict with other files. When it is graded, it will be executed as two processes of Azzurro and Bordeaux. The process of Azzurro and the process of Bordeaux cannot share global variables.
  • Your program must not use the standard input and the standard output. Your program must not communicate with other files by any methods. However, your program may output debugging information to the standard error.

Compilation and Test Run

You can download an archive file from the contest webpage which contains the sample grader to test your program. The archive file also contains a sample source file of your program.

The sample grader is the file grader.cpp\texttt{grader.cpp}. In order to test your program, put 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} in the same directory, and run the following command to compile your programs.

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

Instead, you may run compile.sh\texttt{compile.sh} contained in the archive file. In this case, run the following command to compile your programs.

./compile.sh

When the compilation succeeds, the executable file grader is generated.

Note that the actual grader is different from the sample grader. The sample grader will be executed as a single process, which will read input data from the standard input and write the results to the standard output.

In the actual judging grader, the path chosen by Chiaro is fixed in advance. That is, the path selected by Chiaro is determined before the functions Azzurro\texttt{Azzurro} and Bordeaux\texttt{Bordeaux} in your submitted program are called.

Input Format

The sample grader reads the following data from the standard input.

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

Here, RiR_i (1≤i≤Q1 \leq i \leq Q) is a string of length 2(N−1)2(N-1) consisting of exactly N−1N-1 occurrences of 'D \texttt{D}' and N−1N-1 occurrences of 'R \texttt{R}'. This string represents the path chosen by Chiaro in the ii-th turn, which starts from (0,0)(0,0) and reaches (N−1,N−1)(N-1,N-1) by repeatedly moving only to an adjacent cell either down or to the right. Specifically, starting from (0,0)(0,0), for each j=1,2,⋯ ,2(N−1)j=1,2,\cdots,2(N-1), if the jj-th character of RiR_i is 'D \texttt{D}', the move is to the adjacent cell below; if it is 'R \texttt{R}', the move is to the adjacent cell to the right. Repeating this process results in reaching (N−1,N−1)(N-1,N-1).

Output Format

The sample grader outputs the following information to the standard output (quotes for clarity).

  • If your program is judged as correct, it writes the value of L∗L^* as “Accepted: 26\texttt{Accepted: 26}”. For the value of L∗L^*, see Grading.
  • If your program is judged as any type of Wrong Answer, the sample grader writes its type as “Wrong Answer [1]”.

If your program satisfies the conditions of several types of Wrong Answer, the sample grader reports only one of them. The sample grader may terminate the execution when one of the conditions for wrong answer is met.

Hint

Sample Communication

Here is a sample input for the sample grader and corresponding function calls.

Input

2 2
1
B
RD
3
ABB
DR

Sample Function Calls

Function call Return value
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"}

This sample input consists of Q(=2)Q(=2) turns, and in each turn an N×NN \times N grid (N=2N = 2) is used. In this example, the first turn proceeds as follows.

  1. Azzurro colors (00,11) and (11,00) blue, and (00,00) and (11,11) red. He then hands the grid to Chiaro.

  2. Chiaro performs the following operations out of sight of Azzurro and Bordeaux.

    (a) He selects the path (00,00) →\to (00,11) →\to (11,11) as a path from (00,00) to (N−1N - 1,N−1N - 1) by repeatedly moving only to an adjacent cell either down or to the right.

    (b) For the three cells (00,00),(00,11),(11,11) on this path, he changes their colors. As a result, the colors of (00,00),(00,11),(11,11) become blue, red, and blue, respectively.

  3. Bordeaux can win this turn by writing "B" on the paper.

The second turn proceeds as follows.

  1. Azzurro colors all cells blue. He then hands the grid to Chiaro.

  2. Chiaro performs the following operations out of sight of Azzurro and Bordeaux.

    (a) He selects the path (00,00) →\to (11,00) →\to (11,11) as a path from (00,00) to (N−1N - 1,N−1N - 1) by repeatedly moving only to an adjacent cell either down or to the right.

    (b) For the three cells (00,00),(11,00),(11,11) on this path, he changes their colors. As a result, the colors of (00,00),(11,00),(11,11) all become red.

  3. Bordeaux can win this turn by writing "ABB" on the paper.

Note that this sample input does not satisfy the constraints of the problem. The file sample-01-in.txt\texttt{sample-01-in.txt}, which can be downloaded from the contest site, corresponds to Sample Input 1. The file sample-02-in.txt\texttt{sample-02-in.txt}, which can be downloaded from the contest site, is a sample input that satisfies the constraints.

Constraints

All the input data satisfy the following conditions.

  • 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).
  • QQ, LiL_i (1≤i≤Q1 \leq i \leq Q) are integers.
  • SiS_i (1≤i≤Q1 \leq i \leq Q) is a string of length LiL_i consisting of 'A\texttt{A}' and 'B\texttt{B}'.
  • RiR_i (1≤i≤Q1 \leq i \leq Q) is a string of length 2(N−1)2(N-1) consisting of exactly N−1N-1 occurrences of 'D \texttt{D}' and N−1N-1 occurrences of 'R \texttt{R}'.

Grading

If your program is judged as any type of Wrong Answer [1] or Wrong Answer [2] (see Implementation Details), Time Limit Exceeded, Memory Limit Exceeded, or Runtime Error, in any testcase, your score is 00 points.

Otherwise, let L∗L^* be the minimum of the following values for all test cases of this task. Your score is calculated as in the following table.

  • The maximum value of LL such that Azzurro and Bordeaux win all the turns satisfying Li≤LL_i \leq L. However, if they win all the turns in the test case, we set L=51L = 51.
The value of L∗L^* Your score
1≤L∗≤281 \leq L^* \leq 28 2L∗2L^* points
29≤L∗≤3929 \leq L^* \leq 39 L∗+28L^* + 28 points
40≤L∗≤5040 \leq L^* \leq 50 67+3(L∗−40)67 + 3(L^* - 40) points
L∗=51L^* = 51 100100 points