The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 3 – Broken Device 2Broken Device 2
Anna and Bruno are gamble masters. They will play a game with D-taro who is the dealer of the game.
In this game, Anna and Bruno stay in diﬀerent rooms. They can communicate with each other using a broken
device only. D-taro gives an integer to Anna. For Anna and Bruno, the purpose of this game is to send the given
integer from Anna to Bruno using the device.
When the game starts, in the beginning, Anna declares an integer m between 1 and 2 000, inclusive. Thenthey play Q rounds. The round i (1 ≤ i ≤ Q) is performed as follows.
1. D-taro gives an integer Ai to Anna.
2. Anna inputs arrays si , ti into the device. Every element of the arrays si , ti should be either 0 or 1. Thearrays si , ti should have the same length, and the length is between 1 and m, inclusive.
3. Let ui be an array obtained from the arrays si and ti by riﬄe shuﬄe (see below). Then the device sends
ui to Bruno.
4. Bruno sends an integer to D-taro. If this integer is the same as the integer Ai given by D-taro to Anna,
Anna and Bruno win for this round.
Write programs which implements the strategies of Anna and Bruno so that theory win for all the Q rounds.

Riffle Shuffle
We say an array Z is obtained from the arrays X and Y by riﬄe shuﬄe if we can divide the elements of thearray Z into two groups so that the following two conditions are satisfied.
• The array consisting of the elements in the first group in the same order is equal to the array X.
• The array consisting of the elements in the second group in the same order is equal to the array Y.
For example, the array Z = [1, 1, 1, 0, 0, 0] is obtained from X = [1, 1, 0] and Y = [1, 0, 0] by riﬄe shuﬄebecause the array consisting of the first, second, fourth elements of Z in the same order is the array [1, 1, 0], andthe array consisting of the third, fifth, sixth elements of Z in the same order is the array [1, 0, 0].
On the other hand, if X = [1, 1, 0], Y = [1, 0, 0]，and Z = [0, 0, 0, 1, 1, 1], the array Z is not obtained from X
and Y by riﬄe shuﬄe.

Broken Device 2– 1 / 6

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 3 – Broken Device 2

Implementation Details
You need to submit two files.
The first file is Anna.cpp. It should implement Anna’s strategy. It should implement the following functions.
The program should include Anna.h using the preprocessing directive #include.
• int Declare()This function is called once in the beginning.
◦ The return value is the integer m declared by Anna.
◦ The integer m should be between 1 and 2 000, inclusive. If this condition is not satisfied, yourprogram is judged as Wrong Answer [1].
• std::pair<std::vector<int>, std::vector<int> > Anna(long long A)
After the function Declare is called, this function is called Q times. The i-th call (1 ≤ i ≤ Q) to thisfunction corresponds to Step 1 and Step 2 for the round i.
◦ The parameter A is the integer Ai given by D-taro to Anna.
◦ The return value is the pair of the two arrays si , ti input by Anna into the device.
◦ Every element of the arrays si , ti should be either 0 or 1. If this condition is not satisfied, yourprogram is judged as Wrong Answer [2].
◦ Both of the lengths of the arrays si , ti should be between 1 and m, inclusive. If this condition is notsatisfied, your program is judged as Wrong Answer [3].
◦ The arrays si , ti should have the same length. If this condition is not satisfied, your program isjudged as Wrong Answer [4].
The second file is Bruno.cpp. It should implement Bruno’s strategy. It should implement the following
function. The program should include Bruno.h using the preprocessing directive #include.
• long long Bruno(std::vector<int> u)
After Anna inputs the arrays into the device, this function is called once. In total, this function is called
Q times. The i-th call (1 ≤ i ≤ Q) to this function corresponds to Step 3 and Step 4 for the round i.
◦ The parameter u is the array ui sent by the device to Bruno for the round i.
◦ The return value is the integer sent by Bruno to D-taro.
◦ The return value should be the same as the integer Ai given by D-taro to Anna. If this condition is
not satisfied, your program is judged as Wrong Answer [5].

Broken Device 2– 2 / 6

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 3 – Broken Device 2Important 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 internalfunctions should be declared in an unnamed namespace to avoid confliction with other files. When it isgraded, it will be executed as two processes of Anna and Bruno. The process of Anna and the process ofBruno 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 tothe standard error.

Compilation and Test Run
You can download an archive file from the contest webpage which contains the sample grader to test yourprogram. The archive file also contains a sample source file of your program.
The sample grader is the file grader.cpp. In order to test your program, put grader.cpp，Anna.cpp，
Bruno.cpp，Anna.h，Bruno.h in the same directory, and run the following command to compile your programs.
g++ -std=gnu++17 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp
When the compilation succeeds, the executable file grader is generated.
Note that the actual grader is diﬀerent 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.

Broken Device 2– 3 / 6

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 3 – Broken Device 2Input for the Sample GraderThe sample grader reads the following data from the standard input.
QA1
A2..
.
AQOutput of the Sample Grader
The sample grader outputs the following information to the standard output (quotes for clarity).
• If your program is judged as correct, it writes the return value m of the function Declare as“Accepted: 2000”.
• If your program is judged as any one 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.
When the sample grader is executed, the riﬄe shuﬄe for each round is calculated using pseudo random
numbers. Their results do not change for executions. In order to change the seed of pseudo random numbers,execute the sample grader by the following way.
./grader 2022
The first argument should be an integer.

Broken Device 2– 4 / 6

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying TrialMarch 20–23, 2022 (Komaba, Tokyo)
Contest 3 – Broken Device 2Constraints• 1 ≤ Q ≤ 1 000.
• 1 ≤ Ai ≤ 1 000 000 000 000 000 000 (= 1018 ) (1 ≤ i ≤ Q).

Subtasks1. (5 points) Ai ≤ 2 000 (1 ≤ i ≤ Q).
2. (5 points) Ai ≤ 4 000 000 (1 ≤ i ≤ Q).
3. (3 points) Ai ≤ 10 000 000 (= 107 ) (1 ≤ i ≤ Q).
4. (12 points) Ai ≤ 100 000 000 (= 108 ) (1 ≤ i ≤ Q).
5. (15 points) Ai ≤ 100 000 000 000 (= 1011 ) (1 ≤ i ≤ Q).
6. (60 points) No additional constraints. For this subtask, your score is calculated as follows.
• Let m∗ be the maximum of the integers m declared by Anna for all test cases of this subtask.
• Your score is as follows.
The value of m∗Score

201 ≤ m∗ ≤ 2 000( ∗)mpoints (rounded down to the nearest integer)
40 − 25 × log10 200

161 ≤ m∗ ≤ 200

40 points∗156 ≤ m ≤ 160

44 points

151 ≤ m∗ ≤ 155

48 points∗

146 ≤ m ≤ 150

52 points

141 ≤ m∗ ≤ 145

56 points∗m ≤ 140

60 points

Broken Device 2– 5 / 6

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 3 – Broken Device 2Sample Communication
Here is a sample input for the sample grader and corresponding function calls.
Sample Input 1

Sample Function Calls
CallReturn Value

2Declare()442

Anna(42)([0, 0, 1, 0], [1, 1, 0, 1])

2000

Bruno([1, 0, 0, 1, 0, 1, 0, 1])

42

Anna(2000)([0, 1], [0, 0])

Bruno([0, 0, 1, 0])2000

In this sample input, there are Q (= 2) rounds. For the round 1, D-taro gives the integer A1 (= 42) to Anna.
For the round 2, D-taro gives the integer A2 (= 2000) to Anna.
This sample input satisfies the constraints of all the subtasks.

Broken Device 2– 6 / 6