結果

問題 No.3766 PQ Disjunction
コンテスト
ユーザー 👑 potato167
提出日時 2026-10-17 13:33:15
言語 C++17
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 39 ms / 1,000 ms
+ 221µs
コード長 1,500 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,398 ms
コンパイル使用メモリ 217,040 KB
実行使用メモリ 17,464 KB
最終ジャッジ日時 2026-10-17 13:33:56
合計ジャッジ時間 5,726 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/*
略解：
i & K が等しい整数を同じグループに分ける。

各グループの要素を昇順に並べた列を v とする。
|v| = s とし、s 以上の最小の 2 冪を m とする。
添字 i = m-s, ..., s-1 の要素について、
v[i] と v[m-1-i] をペアにする。

このとき、ペアの AND は必ずグループのキーと等しい。
残った先頭 m-s 個の要素について同じ操作を繰り返す。

全グループを処理すると、AND の OR は K になる。
ただし、K が N 以上の 2 冪のビットを含む場合は不可能。

計算量は O(N)。
*/

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    int lim = 1;
    while (lim < N) lim *= 2;

    if (K >= lim) {
        cout << "No\n";
        return 0;
    }

    vector<vector<int>> G(N);
    for (int i = 0; i < N; i++) {
        G[i & K].push_back(i);
    }

    vector<int> P, Q;

    for (auto &v : G) {
        while (!v.empty()) {
            int s = v.size();
            int m = 1;
            while (m < s) m *= 2;

            for (int i = m - s; i < s; i++) {
                P.push_back(v[i]);
                Q.push_back(v[m - 1 - i]);
            }

            v.resize(m - s);
        }
    }

    cout << "Yes\n";
    for (const auto &v : {P, Q}) {
        for (int i = 0; i < N; i++) {
            cout << v[i] << (i == N - 1 ? "\n" : " ");
        }
    }
}
0