Interactive Sgn Recovery

This is an interactive problem. On the AutoLab platform there is a strange computer with a fixed bit length of \(k = 8192 = 2^{13}\). Each integer is stored in \(k\) consecutive bits. For a given integer, suppose that after reading these bits from lower to higher order we obtain a binary string \(S\) of length \(k\). With indices starting at 0, the integer value corresponding to \(S\) is defined as

[ f(S) = \sum_{i=0}^{k-1} [S_i=1] ; sgn_i ; 2^i, ]

where \(sgn = [sgn_0, sgn_1, \ldots, sgn_{k-1}]\) is a pre-defined array with each \(sgn_i \in \{-1,1\}\). It is guaranteed that \(sgn_{k-1} = 1\) and \(sgn_{k-2} = -1\). The values \(sgn_0, sgn_1, \ldots, sgn_{k-3}\) are unknown to you.

Let

[ L = \sum_{i=0}^{k-1} \min{0, sgn_i} ; 2^i, \qquad R = \sum_{i=0}^{k-1} \max{0, sgn_i} ; 2^i. ]

It can be shown (proof omitted) that for every integer (x) in the interval ([L, R]) there exists exactly one binary string (T) of length (k) such that (f(T)=x). Hence, one may define the inverse function (g(x)) satisfying (f(g(x))=x) for all (x) in the appropriate set (S).

Furthermore, the computer defines addition \(\oplus\) between two stored integers \(x, y \in S\) as follows:

[ x \oplus y \overset{def}{=} \Big((x+y-L+2^k) \bmod 2^k\Big) + L. ]

It is clear that \(x \oplus y \in S\) and that the addition is commutative and associative. You are allowed to query the computer with pairs of \(k\)-bit strings. For each query you provide two \(k\)-bit strings \(x\) and \(y\) (each a binary string of 0s and 1s), and the computer returns the result of

[ g(f(x) \oplus f(y)). ]

Your task is to determine the unknown values \(sgn_0, sgn_1, \ldots, sgn_{k-3}\) with at most \(m\) queries to the provided addition function.

Task:

• You are required to implement a function solve with the following signature:

std::vector<int> solve(int k, int m);

Here:

• k is the word length of the machine (always a fixed constant, for example \(8192\) in the problem description).
• m is the maximum number of queries you are allowed.
• The solve function must return a vector of size \(k\) where the \(i^{th}\) element is the determined value of sgn_i.

You can use the following interactive function to perform addition on the computer:

std::bitset<8192> Add(std::bitset<8192> x, std::bitset<8192> y);

This function takes two \(k\)-bit bitsets and returns a \(k\)-bit bitset corresponding to \(g(f(x) \oplus f(y))\). Note that the testing system will call the solve function exactly once.

Note: In this problem the interaction is deterministic. Although you have the chance to query information about \(sgn_i\) via the Add function, the secret array sgn is fixed at the start and does not change during the interaction.

inputFormat

The input is read from standard input and consists of:

• The first line contains two integers \(k\) and \(m\) separated by a space.
• The following line contains \(k\) integers representing the array sgn, where \(sgn_{k-1} = 1\) and \(sgn_{k-2} = -1\).

outputFormat

Output a single line with \(k\) integers (separated by a space) representing the determined values of \(sgn_0, sgn_1, \ldots, sgn_{k-1}\).

sample

8 1
1 1 1 1 1 1 -1 1

1 1 1 1 1 1 -1 1