問題一覧 > 通常問題

No.3271 PQ Dot Product

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 13
作問者 : apricity / テスター : 👑 qand
お気に入りにしたユーザー ProblemId : 12552 / 自分の提出
問題文最終更新日: 2025-09-12 01:31:05
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 482 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。