背景

提交注意事项：

1. 不要引入头文件。
2. 在文件头加入

   #include <vector>
   int query(std::vector<int>);
   

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 函数。

你应当实现以下的函数：

int solve(int N)

• 返回 $|X|$。
• 该函数被调用恰好一次。

你可以调用以下的函数：

int query(vector<int> 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
2
2 0 1
3 2 3 4

2
3

提示

数据范围

• $6\le N\le 1\, 000$；
• $1\le |X|\le 50\, 000$；
• 对于任意 $S\in X$，$|S|\in \{2,3\}$；
• 交互库是非自适应的。换言之，$X$ 在调用 solve 前已固定。

子任务

• 特殊性质 $\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$。

评测程序最初调用以下函数：

solve(6)

选手的代码可能会进行如下交互：

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) 的返回值来提交答案。