P15586 [KTSC 2026] 50,000 Sauces / 50,000 Sauces

Submission notes: 1. Do **not** include any header files. 2. Add the following at the top of the file: ```cpp #include int query(std::vector); ``` 3. Submit using $\texttt{C++\,\red{20/23}}$.

**This is an interactive problem. In this problem, the interactive library is non-adaptive.** You are given a positive integer $N$. There is a hidden family of sets $X$. Each element $S$ of $X$ is a subset of $\{0,1,\ldots,N-1\}$. Here, $|S|$ is $2$ or $3$. Note that, by definition, a set cannot contain duplicate elements. You may make the following queries multiple times, and your goal is to determine $|X|$ using as few queries as possible: > **Query** > > Given $Y\subseteq \{0,1,\ldots, N-1\}$ with $|Y|\le \lceil \frac{N}{2} \rceil + 1$. > > The interactive library returns $f(Y)=|\{S\in X \mid S \subseteq Y \}|$. Determine $|X|$ using as few queries as possible. ### Implementation Details **This is a function-based interactive problem**. You do not need to, and must not, implement the `main` function. You should implement the following function: ```cpp int solve(int N) ``` - Return $|X|$. - This function is called exactly once. You may call the following function: ```cpp int query(vector Y) ``` - The elements in $Y$ must be pairwise distinct. - It must hold that $0\le Y[i]\le N-1$. - It must hold that $|Y|\le \lceil \frac{N}{2} \rceil + 1$. - This function returns $f(Y)=|\{S\in X \mid S \subseteq Y \}|$. - In each test case, this function can be called at most $3\,000$ times. Your source code must not call any input/output functions.

The input format of the sample grader program is as follows: * Line $1$: $N$ * Line $2$: $K$ $(= |X|)$ * For each $0 \le i < K$: * Line $3 + i$: $L$ $a_0$ $a_1$ ... $a_{L-1}$ * $2 \le L \le 3$ * $0 \le a_j \le N - 1$ * $a_0, a_1, \ldots, a_{L-1}$ are all distinct. * $\{a_0, a_1, \ldots, a_{L-1}\}$ is an element of the set family $X$.

The sample grader program outputs the value returned by your code in the `solve` function and the number of calls to `query` in the following format: * Line $1$: the value $x$ returned by the `solve` function * Line $2$: the number of calls to `query`, $Q$

### Constraints - $6\le N\le 1\, 000$. - $1\le |X|\le 50\, 000$. - For any $S\in X$, $|S|\in \{2,3\}$. - The interactive library is non-adaptive. In other words, $X$ is fixed before `solve` is called. ### Subtasks | ID | Score | $N\le $ | Special Property | | :-: | :-: | :-: | :-: | | $1$ | $11$ | $500$ | $\text{AB}$ | | $2$ | $32$ | $500$ | $\text{A}$ | | $3$ | $25$ | $1\, 000$ | $\text{B}$ | | $4$ | $32$ | $1\, 000$ | | - Special property $\text{A}$: For any two different $S_i,S_j\in X$, $S_i\cap S_j=\varnothing$. - Special property $\text{B}$: For any $S\in X$, $|S|=2$. ### Scoring In each subtask, if there is any case where the answer $|X|$ is incorrect, then this subtask gets $0$ points. Otherwise, let $Q$ be the maximum number of calls to `query` among all test cases in that subtask. The score is calculated by the following rules: - For subtasks $1,2$, if $Q\le 3\, 000$, you get full score. - For subtasks $3,4$: - If $41\lt Q\le 3\, 000$, you get $\displaystyle (0.5 + \frac{41}{2Q})$ times the full score of the subtask. - If $Q\le 41$, you get full score. ### Example $N = 6$, $X = \{\{0,1\}, \{2,3,4\}\}$. $|X| = 2$. The maximum size of a query set is $\lfloor 6/2 \rfloor + 1 = 4$. The grader program initially calls the following function: ```cpp solve(6) ``` Your code may interact as follows: ```cpp query(0, 1, 2) query(2, 3, 4) query(0, 2, 3, 5) ``` * Since $\{0, 1\} \subseteq \{0, 1, 2\}$ and $\{2, 3, 4\} \not\subseteq \{0, 1, 2\}$, `query(0, 1, 2)` returns $1$. * Since $\{0, 1\} \not\subseteq \{2, 3, 4\}$ and $\{2, 3, 4\} \subseteq \{2, 3, 4\}$, `query(2, 3, 4)` returns $1$. * Since $\{0, 2, 3, 5\}$ does not contain any element of $X$, `query(0, 2, 3, 5)` returns $0$. Your code submits the answer by returning $2$ as the return value of `solve(6)`. Translated by ChatGPT 5