P15586 [KTSC 2026] 五万酱汁 / 50,000 Sauces
题目背景
提交注意事项：
1. **不要**引入头文件。
2. 在文件头加入
```cpp
#include
int query(std::vector);
```
3. 使用 $\texttt{C++\,\red{20/23}}$ 提交。
题目描述
**这是一道交互题。本题中，交互库是非自适应的。**
给定正整数 $N$。
有一个隐藏的集族 $X$。$X$ 的每个元素 $S$ 都是 $\{0,1,\ldots,N-1\}$ 的子集。这里，$|S|$ 是 $2$ 或 $3$。注意，根据定义，集合不能包含重复元素。
你可以进行若干次以下的询问，目标是找出 $|X|$：
> **询问**
>
> 给定 $Y\subseteq \{0,1,\ldots, N-1\}$ 满足 $|Y|\le \lceil \frac{N}{2} \rceil + 1$。
>
>
> 交互库回答 $f(Y)=|\{S\in X \mid S \subseteq Y \}|$。
用尽量少的询问次数找出 $|X|$。
### 实现细节
**这是一道函数式交互题**。你不必，也不应实现 `main` 函数。
你应当实现以下的函数：
```cpp
int solve(int N)
```
- 返回 $|X|$。
- 该函数被调用恰好一次。
你可以调用以下的函数：
```cpp
int query(vector Y)
```
- $Y$ 中的元素必须两两不同。
- 必须有 $0\le Y[i]\le N-1$。
- 必须有 $|Y|\le \lceil \frac{N}{2} \rceil + 1$。
- 该函数返回 $f(Y)=|\{S\in X \mid S \subseteq Y \}|$。
- 每个测试点中，该函数最多可调用 $3\,000$ 次。
你的源代码中不应调用任何输入/输出函数。
输入格式
示例评测程序的输入格式如下：
* 第 $1$ 行：$N$
* 第 $2$ 行：$K (= |X|)$
* 对于每个 $0 \le i < K$：
* 第 $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}$ 各不相同。
* $\{a_0, a_1, \ldots, a_{L-1}\}$ 是集合 $X$ 的一个元素。
输出格式
示例评测程序按以下格式输出你的代码在 `solve` 函数中返回的值以及调用 `query` 的次数：
* 第 $1$ 行：`solve` 函数返回的值 $x$
* 第 $2$ 行：调用 `query` 的次数 $Q$
说明/提示
### 数据范围
- $6\le N\le 1\, 000$；
- $1\le |X|\le 50\, 000$；
- 对于任意 $S\in X$，$|S|\in \{2,3\}$；
- 交互库是非自适应的。换言之，$X$ 在调用 `solve` 前已固定。
### 子任务
| 编号 | 得分 | $N\le $ | 特殊性质 |
| :-: | :-: | :-: | :-: |
| $1$ | $11$ | $500$ | $\text{AB}$ |
| $2$ | $32$ | $500$ | $\text{A}$ |
| $3$ | $25$ | $1\, 000$ | $\text{B}$ |
| $4$ | $32$ | $1\, 000$ | |
- 特殊性质 $\text{A}$：对于任意两个不同的 $S_i,S_j\in X$，$S_i\cap S_j=\varnothing$；
- 特殊性质 $\text{B}$：对于任意 $S\in X$，$|S|=2$。
### 计分方式
在每个子任务中，若有回答 $|X|$ 错误的情况，该子任务得 $0$ 分。
否则，令 $Q$ 为该子任务各测试点中调用 `query` 函数次数的最大值，按照如下规则计算得分：
- 对于子任务 $1,2$，若 $Q\le 3\, 000$，得满分。
- 对于子任务 $3,4$：
- 若 $41\lt Q\le 3\, 000$，得 $\displaystyle (0.5 + \frac{41}{2Q})$ 倍子任务满分；
- 若 $Q\le 41$，得满分。
### 样例
$N = 6$，$X = \{\{0,1\}, \{2,3,4\}\}$。$|X| = 2$。
询问集合的最大大小为 $\lfloor 6/2 \rfloor + 1 = 4$。
评测程序最初调用以下函数：
```cpp
solve(6)
```
选手的代码可能会进行如下交互：
```cpp
query(0, 1, 2)
query(2, 3, 4)
query(0, 2, 3, 5)
```
* 由于 $\{0, 1\} \subseteq \{0, 1, 2\}$ 且 $\{2, 3, 4\} \not\subseteq \{0, 1, 2\}$，`query(0, 1, 2)` 返回 $1$。
* 由于 $\{0, 1\} \not\subseteq \{2, 3, 4\}$ 且 $\{2, 3, 4\} \subseteq \{2, 3, 4\}$，`query(2, 3, 4)` 返回 $1$。
* 由于 $\{0, 2, 3, 5\}$ 不包含 $X$ 的任何元素，`query(0, 2, 3, 5)` 返回 $0$。
选手的代码通过将 $2$ 作为 `solve(6)` 的返回值来提交答案。