問題一覧 > 通常問題

No.1530 Permutation and Popcount

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 28
作問者 : PCTprobabilityPCTprobability / テスター : tatyamtatyam penguinmanpenguinman
11 ProblemId : 6368 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-29 18:21:45

問題文

$\mathrm{popcount}(n)$ を $n$ を $2$ 進数表記した時の $1$ の個数とします。例えば $\mathrm{popcount}(11)=3,\ \mathrm{popcount}(64)=1$ です。

正整数列 $A_1,A_2,\dots,A_K$ に対して $f(A)$ を以下で定義します。

  • $1 \le i,j \le K$ かつ $\mathrm{popcount}(A_i \times A_j) \equiv 0 \pmod 2$ である正整数の組 $(i,j)$ の個数

以下を満たす正整数列の組 $(X_1,X_2,\dots,X_P),(Y_1,Y_2,\dots,Y_Q)$ を構築してください。存在しない場合はそのことを報告してください。

  • $X,Y$ は $(1,2,3,\dots,N)$ を $2$ 個に分割した数列の組である。厳密には以下を満たす。
    • $0 \le P,Q$
    • $P+Q=N$
    • $1 \le X_i \le N$
    • $1 \le Y_j \le N$
    • $i \neq j$ ならば $X_i \neq X_j$
    • $i \neq j$ ならば $Y_i \neq Y_j$
    • $X_i \neq Y_j$
  • $f(X)-f(Y)=M$

入力

$N\ M$

  • 入力は全て整数である。
  • $2 \le N \le 300$
  • $0 \le M \le N^2$

出力

条件を満たす正整数列の組 $(X_1,X_2,\dots,X_P),(Y_1,Y_2,\dots,Y_Q)$ が存在しないならば $-1$ を出力してください。

条件を満たす正整数列の組 $(X_1,X_2,\dots,X_P),(Y_1,Y_2,\dots,Y_Q)$ が存在するならば解を $1$ 個以下の形式で出力してください。

解が複数存在する場合はいずれを出力しても構いません。

$P\ Q$
$X_1\ X_2\ \dots\ X_P$
$Y_1\ Y_2\ \dots\ Y_Q$

サンプル

サンプル1
入力
5 1
出力
3 2
1 2 5
3 4

$f(1,2,5)=4,f(3,4)=3$ なので $f(X)-f(Y)=1$ を満たしています。ほかの条件も全て満たしているためこの出力は正解となります。

サンプル2
入力
6 7
出力
-1

条件を満たす数列の組は存在しません。よって $-1$ を出力してください。

サンプル3
入力
19 43
出力
11 8
13 12 10 18 14 6 5 8 3 16 4 
19 9 17 1 15 7 11 2 

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。