Background

CTT2021 D2T2.

Special reminder: due to Luogu’s interactive mechanism, you cannot include datalab.h in your program. Instead, you must copy the content of datalab.h to the beginning of your file. That is, add the following lines before the solve function in your program:

#include<bitset>
#include<vector>
typedef std::bitset<8192> Bitset;
Bitset Add(Bitset A,Bitset B);
std::vector<int> solve(int k,int LIMIT);

Problem Description

This is an interactive problem.

On the AutoLab platform, there is a strange $k$-bit computer, where $k$ is a fixed constant $8192 = 2^{13}$. The word length of this computer is exactly $\frac{k}{8} = 1024 = 2^{10}$, and it stores integers as follows:

Each integer is stored in $k$ consecutive bits. Suppose the values of these $k$ consecutive bits, arranged in increasing index order, form a length-$k$ binary string $S$ consisting of 0 and 1. Assume $S$ is indexed starting from $0$. Then the integer value corresponding to $S$ is $f(S) = \sum \limits_{i=0}^{k-1} [S_i=1] sgn_i 2^i$, where $sgn$ is a length-$k$ array pre-defined by a certain little W, indexed from $0$, and $\forall 0 \le i < k,sgn_i \in \{-1,1\}$. For some special reason, this computer guarantees $sgn_{k-1} = 1$ and $sgn_{k-2} = -1$. However, you do not know the values of $sgn_0,sgn_1,\cdots,sgn_{k-3}$.

Let $L = \sum \limits_{i=0}^{k-1} \min\{0,sgn_i\} 2^i$, $R = \sum \limits_{i=0}^{k-1} \max\{0,sgn_i\} 2^i$. Then we find that for every $L \le x \le R$, there is exactly one length-$k$ binary string $f(T)$ such that $f(T) = x$ (proof omitted). Let the set of all integers in $[L,R]$ be $S$. Then $f$ is a bijection from $\{0,1\}^n$ to $S$. Therefore, we can define the inverse function $g(x)$ of $f(x)$, and it satisfies $\forall x \in S,f(g(x)) = x$.

Assume $x,y \in S$. Then the addition operation $\oplus$ between two integers on this computer is defined as $x \oplus y \overset{def}{=} (x + y - L + 2^k) \bmod 2^k + L$. It is easy to see that $\forall x,y \in S,x \oplus y \in S$. Thus, addition on this computer is closed. The addition defined by the above rule also satisfies commutativity, associativity, and other properties. Proofs are omitted as well.

Students can obtain information related to $sgn_i$ through a limited number of queries. In each query, you can give the computer two length-$k$ strings $x,y$ containing only $0,1$, and the computer will return the value of $g(f(x) \oplus f(y))$. The task of this assignment is to determine the exact values of $sgn_0,sgn_1,\cdots,sgn_{k-3}$ using no more than $\mathrm{m}$ queries.

Little Z is an extremely clever student, so he tried to use his super brain of $10^3 \mathrm{Hz}$ to compute each interaction result by hand. However, he found that even his processing speed could not keep up with the huge amount of data. Therefore, he asks you to write a program to help him complete this assignment faster.

Task

You do not need to, and should not, implement the main function. You only need to implement the following function:

1. std::vector<int> solve(int k,int m):
   • The input numbers are the computer word length $k$ and the query limit $\mathrm{m}$.
   • You need to return a vector of size $k$, where the $i$-th element represents the value of $sgn_i$ you have determined.

You can call the following function to use the addition operation on AutoLab.

1. std::bitset<8192> Add(std::bitset<8192> x,std::bitset<8192> y):
   • Given two bitsets of size $k$, reading each bitset from low bit to high bit represents a length-$k$ binary string containing only 0 and 1.
   • Returns a bitset of size $k$, representing the value of $g(f(x) \oplus f(y))$. The returned format is the same as the input format.

As required, you can query the addition result of two integers on this computer at most $\mathrm{m}$ times. In other words, you can call the Add function at most $\mathrm{m}$ times.

During judging, the interactive library will call solve exactly once.

This problem guarantees that the array sgn has been completely fixed before the start and will not be dynamically constructed based on the interaction with your program. Therefore, the interactive operations in this problem are deterministic, and you do not need to care about the specific implementation in the interactive library.

The testdata guarantees that under the call limit, the time required by the interactive library does not exceed 1s. The memory used by the interactive library is fixed and does not exceed 128MB.

How to test your program

grader.cpp in the problem directory is a reference implementation of the interactive library we provide. The interactive library implementation used in the final test is different from this reference implementation, so your solution should not depend on the library implementation.

1. You need to compile an executable in this directory using the following command:

   • g++ grader.cpp sample.cpp -o sample -O2 -lm

2. For the compiled executable:

   • The executable will read the following input format from standard input:
     • The first line contains two integers $k,\mathrm{m}$.
     • The next line contains $k$ integers, where the $i$-th number denotes $sgn_i$.
   • After reading, the interactive library will call the function $\texttt{solve}$ exactly once. After your function returns correctly, the interactive library will check whether your computation is correct. If correct, it will output Correct and information related to the number of interactive calls; otherwise, it will output the corresponding error information.

There is a reference code sample.cpp provided by the problem setter in the problem directory. Note that this code is not guaranteed to pass all test cases.

Samples 1 and 2

See the attachment download.

These two samples satisfy the input format of the executable program, so they can be directly input into the executable program.

Hint

Scoring

For any subtask, if the contestant returns an incorrect answer on any test case, or exceeds the query limit, the score is $0$.

Otherwise, suppose within a subtask, the maximum number of queries used among all test points is $a$. Then for each subtask, the contestant’s score is:

• Subtask $1$: $10$.
• Subtask $2$: $15$.
• Subtask $3$: $\min \{75,\lfloor \frac{13800}{\max\{a,1\}} \rfloor \}$.

In other words, Subtask $3$ gets full score if and only if $a \le 184$.

The total score for this problem is the sum of the scores of the three subtasks.

Translated by ChatGPT 5