Background

All the members are thinking about organizing the anniversary celebration, but Xiao Xi just wants to slack off.

So Xiao Xi opened his favorite game.

Problem Description

After playing this game for so long, today Xiao Xi wants to join an event and fill out a questionnaire to see how well he understands the game.

There are a total of $n$ true/false questions on the questionnaire. Poor Xiao Xi found that he cannot do a single question, so he decided to ask his teammate for help.

His teammate is a veteran user of the game and can do all the questions, so Xiao Xi decided to ask the teammate for assistance. Specifically, each time Xiao Xi will ask in the following format:

int ask(int m,vector<int> w,vector<bool> ans)

Here, $m$ indicates the total number of questions in this query, $w_i$ indicates the question number of the $i$-th queried question (you need to ensure that in a single query the $w_i$ are all distinct, since the teammate is very impatient), and $ans_i$ indicates the answer that Xiao Xi believes is correct for the $i$-th question ($0\le i<m$). The teammate will tell him how many questions he got correct in this query.

For example, suppose there are three questions and the answers are $\{0,1,1\}$. If Xiao Xi calls ask(2,[1,3],[1,1]), then the return value is $1$, because question 1 is answered incorrectly and question 3 is answered correctly.

Because there are too many questions, Xiao Xi needs you to write a program to help him obtain the correct answers to all questions.

You do not need to implement the main function. You only need to implement vector<bool> work(int n). The return value should be the answers to questions $1\sim n$. Note that vector<bool> is 0-indexed, so you need to shift your answer array left by 1 position.

Of course, querying is tiring, so Xiao Xi hopes the number of queries is as small as possible. The scoring standard for the number of queries is given in the Hint. Also, although there is no limit on the number of questions in a single query, you should still be careful: if you query too many questions at once, you may get TLE. The problem guarantees that the time complexity of each query is $O(m)$.

For convenience, use $1$ to represent a correct choice and $0$ to represent an incorrect choice.

Input Format

The sample data belongs to the first part and is given in the following format:
$n\\a_{1...n}$
where $a_i$ indicates the correct answer to question $i$.

Output Format

The following shows the error messages $\text{Wrong[x]}$ from grader.cpp:

1. Some $w_i$ in the query is greater than $n$ or less than $1$.
2. Duplicate $w_i$ appears in the query.
3. $m$ does not match the length of $w$ or $ans$.
4. The answers are wrong or the returned array format is incorrect.

After that, grader.cpp will return your number of queries.

3
0 0 1

2

Hint

Sample Explanation

One feasible plan with $2$ queries is shown below.

ask(1,[2],0), the return value is $1$, indicating that the answer to question 2 is $0$.
ask(2,[1,3],[0,1]), the return value is $2$, maybe because the luck is too good and you guessed everything right, so we can conclude that the answers to questions 1 and 3 are $0,1$.
So you can return $\{0,0,1\}$, and the number of queries is $2$.

Of course, if the result of the second query is $1$, then you cannot directly determine the answers. So, guessing has risks.

Constraints

For all testdata, it is guaranteed that $n\le2^{17}$.

To ensure the quality of users' answers and to prevent users from guessing all true/false questions correctly, the questionnaire creator will carefully construct the answer to each question.

Of course, it is guaranteed here that the answers already exist after the questionnaire is made, and they will not be constructed based on your queries.

Assume that for each testdata you made $Q$ queries. The scoring standard is given below. | Range of $Q$ | Score | | :----------: | :----------: | | $(2^{17},+\infty)$ | $0$ | | $2^{17}$ | $10$ | | $(64000,2^{17})$ | $\min(90,\lfloor\frac{2^{17}-Q}{2^{16}}\times100\rfloor)$ | | $(63000,64000]$ | $95$ | | $[0,63000]$ | $100$ |

Note that this problem has multiple test points, and your final score is the minimum score among all testdata.

Implementation details: be sure to add extern "C". You may choose to fill in the functions in problem.cpp, or implement them yourself. When compiling, directly compile and run grader.cpp.

Friendly reminder: if your random approach performs too poorly, even if your number of queries is less than $2^{17}$, your score may still be less than $10$.

Translated by ChatGPT 5