Background

Special Notice.

Some notes when submitting this problem on Luogu (if it differs from the original statement, please follow what is written here):

1. Different from the original problem, you do not need, and should not, include the shop.h header file at the beginning of your program.
2. When submitting, please add the following function declaration in your program:

int query(int *S, int nS, int *T, int nT);

3. Only C++ (including C++, C++11, C++14, C++17) submissions are supported.

Problem Description

Mr. V, Mr. I, and Mr. Y are good friends.

Mr. I recently opened a shop. The shop has $N$ kinds of items (with IDs being integers from $0 \sim N - 1$). Each kind of item has an unlimited supply. The unit price of each item is either $0$ or $1$.

Mr. V wants to know the price of every item. Through some supernatural power, he already knows that among these $N$ items, the number of items priced at $1$ is exactly odd/even, and there is at least one item whose price is $1$.

However, Mr. V does not want to ask Mr. I himself. He chooses the following method: he prepares $+\infty$ money for Mr. Y, and lets Mr. Y run errands for him. Each time, he specifies two non-empty item sets $S, T$ to Mr. Y (items within the same set must be pairwise distinct, i.e. each kind of item can appear at most once in each set). Mr. Y will go to the shop, buy the items in the two sets respectively, bring them back, and tell Mr. V which set has a larger total price. However, when the sums of the two sets are equal, Mr. Y will answer Mr. V according to Mr. I’s instructions.

Carrying many items is tiring, so we define the physical cost of one errand as $\texttt{S} + \texttt{T}$, where $\texttt{S}$ denotes the number of items in set $S$.

Your task is to write a program to help Mr. V decide how to make Mr. Y run errands in a reasonable way, so as to deduce the value of every kind of item. Mr. Y’s stamina is limited, so you cannot make him too tired, i.e. you cannot let his total physical cost exceed a preset threshold $M$.

Implementation Details

You do not need, and should not, implement the main function. You only need to implement the following function:

• find_price(task_id, N, K, ans)
• Here task_id denotes the subtask ID (see Constraints and Rules). $N$ denotes the number of items, and the meaning of $K$ is:
  • If $K = 0$, it means there are an even number of items with value $1$.
  • If $K = 1$, it means there are an odd number of items with value $1$.
• You need to store the computed item prices in the array $\text{ans}[]$, where $\text{ans[i]}$ is the price of the item with ID $i$.

You can make queries to the interactive library by calling the following function:

• query(S, nS, T, nT)
• Here $\text{nS} = \texttt{S}, \text{nT} = \texttt{T}$. Arrays $\text{S [0\ldots (nS - 1)]}$ and $\text{T[0\ldots (nT - 1)]}$ describe the two sets respectively. You must ensure:
  • $\text{nS, nT} > 0$.
  • $\forall 0 \le i < \text{nS} , 0 \le \text{S[i]} < N$.
  • $\forall 0 \le i < \text{nT} , 0 \le \text{T[i]} < N$.
    $\forall$ means “for any”. For example, $\forall 0 \le i < \text{nS} , 0 \le \text{S[i]} < N$ means: “for any $i$ in $[0, \text{nS})$, $\text{S[i]}$ is in $[0, N)$”.
• The time complexity of calling this function once is $\Theta(\text{nS + nT})$. It returns $0$ or $1$, and the meaning is:
  • If the sum of prices of items in set $S$ is larger, return $0$.
  • If the sum of prices of items in set $T$ is larger, return $1$.
  • Otherwise, return $0$ or $1$ according to some unknown rule.
• As stated, we define the cost of one call as $\text{nS + nT}$.

During evaluation, the interactive library may call find_price multiple times (no more than $10$ times). Each call represents a new price-guessing game, and all item prices will be reset.

Input Format

The executable will read input from standard input in the following format:

The first line contains an integer $T ( T \le 100 )$, the number of test groups. For each group:

• The first line contains two integers $\texttt{task\_id}, N$.
• The next line contains a binary string $s$ of length $N$, where $s_i$ denotes the price of item $i$. You need to ensure that at least one item has price $1$.

After reading is finished, the interactive library will call the find_price function $T$ times.

Then the interactive library will check whether your function is correct each time. If all are correct, it will output Correct; otherwise, it will output the corresponding error message.

Hint

Scoring Rules

This problem is first subject to the same limits as non-interactive programming problems. For example, a compilation error will cause the entire problem to score $0$ points; runtime error, exceeding the time limit, exceeding the memory limit, etc. will cause the corresponding test points to score $0$ points. You may only access variables you define yourself and the variables provided by the interactive library and their corresponding memory space. Attempting to access other memory may cause a compilation error or runtime error.

Under the above conditions, in a test point, you get full score if and only if, in every call to find_price:

• Every call to query follows the rules, and the sum of call costs does not exceed $M$.
• Your function correctly computes the array $\text{ans[]}$.

In a test point, if you do not get full score, then you get $0$ points.

Subtasks

Let the upper bound of the total cost be $M$, and denote the answer array as $\text{ans[]}$:

• Subtask 1: $N \le 5, M = 100$.
• Subtask 2: $N \le 10^3, M = 10^6$.
• Subtask 3: $N \le 10^5, M = 100$. It is guaranteed that $\forall i < j < k$, if $\text{ans[i]} = \text{ans[k]}$ then $\text{ans[j]} = \text{ans[i]}$.
• Subtask 4: $N \le 10^4, M = 2 \times 10^5$.
• Subtask 5: $N \le 5 \times 10^4, M = 350100$.
• Subtask 6: $N \le 10^5, M = 500100$.

Note

Mr. I may not be willing to let Mr. V know the price of every item. When the sums are equal, he will answer in his own way.

Subtask Scores

In this contest, the score distribution of test points (or subtasks) depends on whether you are a CTT contestant. The score settings for this problem are as follows:

Luogu uses the CTT scoring scheme when judging.

Translated by ChatGPT 5