P8913 [RC-06] Remake

Please construct $n$ positive integers $a_1 \sim a_n$ that satisfy: - For every even $X \in [L,R]$, there exist $b_1 \sim b_n$ such that for all $1 \le i \le n$, $b_i \in \{-1,1\}$ and $\sum_{1 \le i \le n} a_i b_i = X$. The values of $L$ and $R$ are given in the Constraints. - Let $cnt_i$ be the number of indices $j$ such that $a_j = i$. Then $cnt_i$ must be either $0$ or at least $2$. - $1 \le n \le 40$. To verify that your $a_i$ indeed satisfy the conditions, $Q$ queries will be given. In each query, an even $X \in [L,R]$ is given. You need to output one valid set of $b_i$.

The first line contains two positive integers $M, Q$, where $M$ is the upper bound of $X$. In the testdata, it is guaranteed that $M = 10^9$. In the next $Q$ lines, each line contains one positive even integer $X$. It is guaranteed that $X \in [L,R]$. Note that $L$ and $R$ are not given in the input. You may assume that $L = \min X$ and $R = \max X$.

The first line outputs the number of positive integers you construct, $n$. $(1 \le n \le 40)$. The next line outputs $n$ positive integers $a_1 \sim a_n$. $(1 \le a_i \le 10^9)$. In the next $Q$ lines, each line contains $n$ characters, each being `+` or `-`. Let the $i$-th character be $s_i$, and let the value in this query be $X$. Then it must satisfy $\sum_{1 \le i \le n} a_i([s_i=$ `+` $]-[s_i=$ `-` $]) = X$, where $[P]$ equals $1$ if $P$ is true, and $0$ otherwise. The $a_i$ you output must satisfy the requirements in the statement. # Input Format The first line contains two positive integers $M, Q$, where $M$ is the upper bound of $X$. In the testdata, it is guaranteed that $M = 10^9$. In the next $Q$ lines, each line contains one positive even integer $X$. It is guaranteed that $X \in [L,R]$. Note that $L$ and $R$ are not given in the input. You may assume that $L = \min X$ and $R = \max X$. # Output Format The first line outputs the number of positive integers you construct, $n$. $(1 \le n \le 40)$. The next line outputs $n$ positive integers $a_1 \sim a_n$. $(1 \le a_i \le 10^9)$. In the next $Q$ lines, each line contains $n$ characters, each being `+` or `-`. Let the $i$-th character be $s_i$, and let the value in this query be $X$. Then it must satisfy $\sum_{1 \le i \le n} a_i([s_i=$ `+` $]-[s_i=$ `-` $]) = X$, where $[P]$ equals $1$ if $P$ is true, and $0$ otherwise. The $a_i$ you output must satisfy the requirements in the statement.

This problem has three subtasks. All testdata satisfy: $2 \le M \le 10^9$, $1 \le Q \le 10^5$, $X \in [L,R]$. - Subtask $1$ ($25$ points): $L = 2$, $R = 2 \times 10^5$. - Subtask $2$ ($5$ points): $L = 10^9 - 2 \times 10^5 + 2$, $R = 10^9$. - Subtask $3$ ($70$ points): $L = 2$, $R = M$. Translated by ChatGPT 5