結果

問題 No.3766 PQ Disjunction
コンテスト
ユーザー apricity
提出日時 2026-07-04 04:58:21
言語 PyPy3
(8.0.0 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 83 ms / 1,000 ms
+ 246µs
コード長 1,928 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,412 ms
コンパイル使用メモリ 64,120 KB
実行使用メモリ 78,232 KB
最終ジャッジ日時 2026-10-16 20:50:14
合計ジャッジ時間 7,059 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#!/usr/bin/env pypy3
def solve_k_zero(n):
    if n == 0:
        return []
    if n == 1:
        return [0]
    l = (n-1).bit_length()
    m = 1<<(l-1)
    ans = list(range(m-1, -1, -1))
    for i in range(m):
        if ans[i]+m < n:
            ans[i] += m
    ans += solve_k_zero(n-m)

    x = 0
    for i in range(n):
        x |= i&ans[i]
    assert x == 0

    return ans

def solve_n_power_2(n, k):
    if n == 0:
        return []
    if n == 1:
        return [0]
    if k < n//2:
        first_half = solve_n_power_2(n//2, k)
        for i in range(len(first_half)):
            first_half[i] += n//2
        second_half = solve_k_zero(n//2)
        return first_half + second_half
    else:
        first_half = solve_n_power_2(n//2, k-n//2)
        second_half = solve_k_zero(n//2)
        for i in range(len(second_half)):
            second_half[i] += n//2
        return first_half + second_half

def solve(n, k):
    p = []
    l = (n-1).bit_length()
    if k < 0 or k >= (1<<l):
        print("No")
        return
    if n == 1:
        print("Yes")
        print(0)
        print(0)
        return

    m = 1<<(l-1)
    if n == (1<<l):
        p = solve_n_power_2(n, k)
    elif k < m:
        p = solve_n_power_2(m, k) + solve_k_zero(n-m)
        for i in range(m):
            if p[i]+m < n:
                p[i] += m
    else:
        p = solve_n_power_2(m, k-m) + solve_k_zero(n-m)
        for i in range(m,n):
            p[i] += m

    print("Yes")
    print(*p)
    print(*list(range(n)))
    # chk = [0 for _ in range(n)]
    # for i in range(n):
    #     chk[p[i]] += 1
    # if chk != [1 for _ in range(n)]:
    #     print(n,k)
    #     print(p)
    #     assert False
    #
    # kc = 0
    # for i in range(n):
    #     assert(p[i] != -1)
    #     kc |= (i&p[i])
    # if k != kc:
    #     print(n,k,kc)
    #     print(p)
    #     assert False

n, k = map(int, input().split())
solve(n,k)
0