Discovering the Correct Answers in the Quiz

After playing the game for so long, Xiao Xi wants to participate in an event today by answering a survey to test his understanding of the game. The survey consists of \(n\) True/False questions. Unfortunately, Xiao Xi cannot solve a single one of them. Fortunately, he has a seasoned teammate who knows all the answers. Xiao Xi can ask his teammate for help by using the following query function:

\(int ask(int m, vector w, vector ans)\)

• \(m\) is the number of questions in the query.
• \(w_i\) is the question number of the \(i\)-th queried question (all \(w_i\) in one query must be distinct).
• \(ans_i\) is Xiao Xi's guess for the \(i\)-th question (using 1 to denote a correct answer and 0 for an incorrect answer).

The teammate will return the number of questions in this query that were answered correctly. For example, if there are three questions with the correct answers \(\{0,1,1\}\) and Xiao Xi calls ask(2, [1, 3], [1, 1]), then he will get a return value of 1 because his guess for the first question is wrong and for the third is correct.

Your task is to help Xiao Xi determine the correct answers for all \(n\) questions by implementing the function:

vector<bool> work(int n)

The returned vector should contain the answers for questions 1 through \(n\) but shifted left by one (i.e. the answer for question 1 is stored at index 0, question 2 at index 1, etc.).

Note: Although you do not need to implement the main function, in the final submission you should write a complete program that reads from input and writes to output. Also, since a query has a time complexity of \(O(m)\) (where \(m\) is the number of questions in that query), you should aim to minimize the number of queries (and the number of questions per query to avoid TLE).

Hint: You can first perform a baseline query by guessing 0 (i.e. false) for all questions. Then, for each question, flip the guess and observe how the number of correct answers changes. If flipping question \(i\) results in an increase of 1 in the returned count, then the correct answer is 1; if it decreases by 1, then the correct answer is 0.

In this problem, we use 1 to indicate a correct answer and 0 to indicate an incorrect one.

inputFormat

The input consists of two lines:

1. The first line contains a single integer \(n\), the number of questions.
2. The second line contains \(n\) space-separated integers (each 0 or 1), representing the hidden correct answers for questions 1 through \(n\).

This hidden data simulates the teammate's correct answers.

outputFormat

Output the discovered answers as \(n\) space-separated integers (each 0 or 1) in one line. The \(i\)-th output corresponds to the answer for question \(i\) (remember: the vector is shifted left by one).

sample

3
0 1 1

0 1 1