P5208 [WC2019] Mr. I’s Shop.

### 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: ```cpp int query(int *S, int nS, int *T, int nT); ``` 3. Only `C++` (including `C++`, `C++11`, `C++14`, `C++17`) submissions are supported.

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.

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.

N/A

#### 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: | Subtask ID | 1 | 2 | 3 | 4 | 5 | 6 | | :------------: | :----: | :----: | :----: | :----: | :----: | :----: | | CTT Score | $20$ | $11$ | $9$ | $12$ | $17$ | $31$ | | Non-CTT Score | $31$ | $21$ | $13$ | $9$ | $11$ | $15$ | **Luogu uses the CTT scoring scheme when judging.** Translated by ChatGPT 5