Background

Original link: https://oier.team/problems/X5F。

$\small\text{The Border of \textbf{Divinity}}.$

Problem Description

This is an interactive problem. Only C++ submissions are supported, and C++14 (GCC 9) is not supported.

Hikari and Tairitsu invented a new game using their glass shards.

There are $n$ piles of shards, numbered from $0$ to $n-1$.

$a$ is a positive integer sequence of length $n$ with indices $0\sim n-1$, where $a_i$ means the number of shards in pile $i$.

They take turns to operate. Each move is as follows:

• Choose a pile $i$, take out at least one shard and discard it.
• Then distribute the remaining shards in pile $i$ arbitrarily among all non-empty piles. In particular, you may put them back into the original pile.

Hikari goes first. The player who cannot make a move loses.

You will play as either Hikari or Tairitsu, and play against the other one.

Specifically, given $a_0, a_1, \ldots, a_{n-1}$, you need to decide whether to be the first or second player, and then play this game on $a_0, a_1, \ldots, a_{n-1}$ with the interactive library.

Interaction Format

This problem uses multiple test cases and uses bundled judging.

Your program does not need to, and must not, include a main function.

You only need to implement the following $3$ functions:

bool Init(int n, int op, std::vector<int> a);

• This function is used for initialization and preprocessing.
• Here $n$ is the number of piles as described, and $op$ is the subtask index.
• $a$ is a std::vector<int> of length $n$ with indices $0\sim n-1$, representing the sequence above.
• You need to return a value in $\{0,1\}$. Returning $0$ means you choose to play first as Hikari, and returning $1$ means you choose to play second as Tairitsu.

void Get(std::vector<int> a);

• This function is used for your program to receive the sequence after the interactive library makes a move.
• $a$ is a std::vector<int> of length $n$, representing the resulting sequence after the library’s move.

std::vector<int> Play();

• This function is used for your program to return the sequence after you make a move.
• You need to return a std::vector<int> $a$ of length $n$, representing the resulting sequence after your move.

Each test point contains multiple test cases. For each test case within a test point, the interaction process is:

• Call Init() once.
• If the contestant chooses to go first, call Play(); otherwise skip this step.
• The library makes one move on $a$ and then calls Get().
• Then the library alternates calling Play() and Get(), guaranteeing that in every two consecutive calls, exactly one is Play() and one is Get().
• In particular, if after some Play() call the library moves $a$ into a terminal state, or if the library cannot move, then it will decide the result and terminate this test case, proceeding to the next one. That is, the library will not call Get() one more time at the end.

This problem will use a custom checker to score your interaction process. See [Scoring] for details。

Input Format

See [Notes / Hint]。

Output Format

See [Notes / Hint]。

2 0
10
1 1 4 5 1 4 1 9 1 9
2
1 1

AC

Hint

This problem uses multiple test cases.

[Sample Explanation]

The sample consists of two test cases.

In the first test case, choosing to go first as Hikari guarantees a win.

In the second test case, choosing to go second as Tairitsu guarantees a win.

[Notes / Hint]

The attachment provides grader.cpp and sample.cpp. sample.cpp is a sample contestant program, which you may build upon. grader.cpp is the provided interactive library. The strategy in the provided library is not the final library’s strategy, so your implementation must not rely on the library’s implementation.

You need to place your program game.cpp and grader.cpp in the same directory, and compile in that directory using the following command to obtain the executable game(.exe):

g++ -o game grader.cpp game.cpp -O2 -std=c++14

The executable reads input from standard input in the following format:

• The first line contains two positive integers $T$ and $op$, where $T$ is the number of test cases, and $op$ is the subtask index. Only the sample has $op=0$.
• For each test case, the input format is:
  • The first line contains a positive integer $n$, the length of sequence $a$.
  • The second line contains $n$ positive integers, representing $a_0,a_1,\ldots,a_{n-1}$.

When testing locally, make sure your input and interaction format meet the requirements. Otherwise, we do not guarantee the interactive library will run correctly.

If your input and interaction format are valid and there is no runtime error, the provided interactive library will output:

• AC if you successfully defeat the interactive library.
• WA otherwise.

Your program must not read from or write to standard input/output. Otherwise it will be considered an attack on the interactive library.

[Scoring]

This problem will use a custom checker to score your interaction process. In each test point, if you exceed the time limit, exceed the memory limit, or encounter a runtime error, your score is $0$. Otherwise, your score depends on your performance during interaction:

• Parameter $S$ depends on your performance during interaction:
  • If in every test case of the test point, you always choose the correct first/second role and always defeat the interactive library, then $S=1$.
  • If in every test case of the test point, you always choose the correct first/second role but make an invalid move or lose to the interactive library, then $S=0.2$.
  • If in every test case of the test point, you choose the wrong first/second role at least once but still defeat the interactive library in all test cases, then if $op\in \{4,5\}$, $S=1$; otherwise $S=0.6$.
  • Otherwise, $S=0$.
• Your final score for this test point is $S\times score$, where $score$ is the score of the subtask containing this test point.
• Your final score for a subtask is the minimum score among all test points within that subtask.

[Constraints]

This problem uses bundled judging.

• Special property A: The interactive library’s strategy is to choose a non-empty pile, take away some shards, and put the remaining shards back into the original pile.
• Special property B: The interactive library’s strategy is to choose a non-empty pile, take away some shards, and put all remaining shards into a single pile (possibly the original pile).

For all data, $1 \le T\le 2000$, $1 \le op \le 6$, $1 \le n\le 2000$, $1 \le a_i\le 2000$, $1 \le \sum a_i \le 4000$, $1 \le\sum n\le 2000$, $1 \le \sum\sum a_i\le 4000$.

It is guaranteed that within each test point, the number of calls to Init() does not exceed 2000, and the total number of calls to Get() and Play() does not exceed 4000. When the contestant’s interaction format is correct, the running time of the interactive library itself is always no more than 500ms.

Translated by ChatGPT 5