No.3271 PQ Dot Product
Problem Statement
You are given positive integers $N,K$. Determine whether there exists a pair $(P = (P_1, P_2,\dots, P_N), Q = (Q_1, Q_2,\dots, Q_N))$ of permutations of $(1,2,\dots,N)$ satisfying the following condition, and if one exists, show an example.
- $\displaystyle\sum_{i=1}^{N} P_i Q_i = K$.
Input
$N\ K$
- All inputs are integers.
- $1 \le N \le 2\times 10^5$
- $1 \le K \le 10^{16}$
Output
If no pair $(P,Q)$ satisfying the condition exists, print No.
If one exists, print Yes on the first line, $P$ on the second line, and $Q$ on the third line, in the following format.
Yes $P_1\ P_2\ \dots\ P_N$ $Q_1\ Q_2\ \dots\ Q_N$If there are multiple pairs satisfying the condition, any of them will be accepted.
Sample
Sample 1
Input
4 22
Output
Yes 4 2 1 3 2 4 3 1
For $P = (4,2,1,3), Q = (2,4,3,1)$, we have $\displaystyle\sum_{i=1}^{4} P_i Q_i = 4\times 2 + 2\times 4 + 1\times 3 + 3\times 1 = 22$.
Sample 2
Input
6 8
Output
No
No pair $(P,Q)$ satisfying the condition exists.
Sample 3
Input
7 123
Output
Yes 1 2 3 4 5 6 7 3 2 7 1 4 6 5
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
apricity