結果

問題 No.3223 K-XOR Increasing Sequence
コンテスト
ユーザー Drtever
提出日時 2026-09-04 17:41:16
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 42 ms / 2,000 ms
+ 966µs
コード長 2,587 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,565 ms
コンパイル使用メモリ 172,060 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2026-09-04 17:41:33
合計ジャッジ時間 11,220 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 71
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 优化输入输出流速度
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, K;
    long long X, Y;
    if (!(cin >> N >> K >> X >> Y)) return 0;

    // Y = 0 永远无解
    if (Y == 0) {
        cout << "No\n";
        return 0;
    }

    // K = 1 必须严格单调递增
    if (K == 1) {
        if (X + N - 1 <= Y) {
            cout << "Yes\n";
            for (int i = 0; i < N - 1; ++i) {
                cout << X + i << " ";
            }
            cout << Y << "\n";
        } else {
            cout << "No\n";
        }
        return 0;
    }

    // X > 0 的情况，使用异或和为 0 的周期序列
    if (X > 0) {
        cout << "Yes\n";
        vector<long long> c(K);
        c[0] = X;
        if (K == 2) {
            c[1] = X;
        } else {
            for (int i = 1; i < K - 1; ++i) c[i] = 1;
            long long xs = X;
            for (int i = 1; i < K - 1; ++i) xs ^= c[i];
            
            if (xs == 0) { // 避免最后补成 0
                c[K - 2] = 2;
                xs = X;
                for (int i = 1; i < K - 1; ++i) xs ^= c[i];
            }
            c[K - 1] = xs;
        }
        for (int i = 0; i < N - 1; ++i) {
            cout << c[i % K] << " ";
        }
        cout << Y << "\n";
        return 0;
    }

    // X == 0, K >= 2 的情况
    if (N == K + 1) {
        cout << "Yes\n";
        for (int i = 0; i < K; ++i) cout << 0 << " ";
        cout << Y << "\n";
        return 0;
    }

    if (N == K + 2) {
        if (Y == 1) {
            cout << "No\n";
        } else {
            cout << "Yes\n";
            cout << 0 << " " << 2 << " ";
            for (int i = 0; i < K - 2; ++i) cout << 0 << " ";
            cout << 3 << " " << Y << "\n";
        }
        return 0;
    }

    // N >= K + 3
    cout << "Yes\n";
    if (K == 2) {
        cout << 0 << " " << 1 << " ";
        for (int i = 2; i < N - 1; ++i) cout << 3 << " ";
        cout << Y << "\n";
        return 0;
    }

    // K >= 3 构造异或和恒为 0 且平稳过渡的块 Z
    vector<long long> Z(K);
    if (K % 2 == 1) {
        for (int i = 0; i < K - 2; ++i) Z[i] = 1;
        Z[K - 2] = 2;
        Z[K - 1] = 3;
    } else {
        Z[0] = 2; Z[1] = 3;
        for (int i = 2; i < K - 2; ++i) Z[i] = 1;
        Z[K - 2] = 2;
        Z[K - 1] = 3;
    }

    cout << 0 << " " << 1 << " ";
    for (int i = 2; i < N - 1; ++i) {
        cout << Z[(i - 2) % K] << " ";
    }
    cout << Y << "\n";
    return 0;
}
0