Background

Submission notes:

1. Do not include any header files.
2. Add the following at the top of the file:

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

3. Submit using $\texttt{C++\,\red{20/23}}$.

Problem Description

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:

int solve(int N)

• Return $|X|$.
• This function is called exactly once.

You may call the following function:

int query(vector<int> 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.

Input Format

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$.

Output Format

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$

6
2
2 0 1
3 2 3 4

2
3

Hint

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

• 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:

solve(6)

Your code may interact as follows:

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