結果

問題 No.3223 K-XOR Increasing Sequence
ユーザー woshinailong
提出日時 2025-08-01 22:52:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,137 bytes
コンパイル時間 665 ms
コンパイル使用メモリ 77,132 KB
実行使用メモリ 18,920 KB
最終ジャッジ日時 2025-08-01 22:52:42
合計ジャッジ時間 19,582 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 13 WA * 57
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric>

// Function to print the vector
void print_vector(const std::vector<long long>& vec) {
    for (size_t i = 0; i < vec.size(); ++i) {
        std::cout << vec[i] << (i == vec.size() - 1 ? "" : " ");
    }
    std::cout << std::endl;
}

int main() {
    // Optimize input/output operations
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    long long n, k, x, y;
    std::cin >> n >> k >> x >> y;

    if (k == 1) {
        if (x + n - 2 < y) {
            std::cout << "Yes" << std::endl;
            std::vector<long long> a(n);
            a[0] = x;
            for (int i = 1; i < n - 1; ++i) {
                a[i] = a[i - 1] + 1;
            }
            a[n - 1] = y;
            print_vector(a);
        } else {
            std::cout << "No" << std::endl;
        }
    } else { // k >= 2
        if (y == 0) {
            std::cout << "No" << std::endl;
        } else {
            std::cout << "Yes" << std::endl;
            std::vector<long long> a(n);
            long long q = (n - 1) / k;
            long long r = (n - 1) % k;

            if (q == 0) { // n - 1 < k  => n <= k. Problem says n > k. This case is not needed.
                          // But as a general case for n > k and n-1 < k => n=k+r, r>0
                a[0] = x;
                long long current_xor_sum = x;
                for (int i = 1; i < n - 1; ++i) {
                    a[i] = 0;
                }
                // To make final XOR sum 0, we can set A_{n-1}
                if (n-1 > 1) {
                    a[n-2] = current_xor_sum;
                }
                a[n - 1] = y;

            } else { // n-1 >= k
                // Construction based on chaining blocks
                // First block: X -> 1
                a[0] = x;
                long long current_val = x;
                
                // Chain q blocks of size k
                for (int i = 0; i < q; ++i) {
                    int start_idx = i * k;
                    a[start_idx] = current_val;
                    if (start_idx + 1 < n) a[start_idx + 1] = current_val;
                    for (int j = 2; j < k && start_idx + j < n; ++j) {
                        a[start_idx + j] = 0;
                    }
                    current_val = 1;
                }
                
                // Remainder part
                int last_block_end = q * k;
                for (int i = last_block_end + 1; i < n - 1; ++i) {
                    a[i] = 1; // Simple fill
                }
                
                a[n-1] = y;

                // A simpler, more direct construction that always works for k>=2, y>0
                std::vector<long long> a_simple(n);
                a_simple[0] = x;
                a_simple[1] = x;
                for(int i = 2; i < k; ++i) {
                    a_simple[i] = 0;
                }
                
                long long xor_sum_window = 0; // X ^ X ^ 0... = 0

                for(int i = k; i < n - 1; ++i) {
                    long long prev_val_out = a_simple[i-k];
                    a_simple[i] = xor_sum_window + 1;
                    xor_sum_window ^= prev_val_out;
                    xor_sum_window ^= a_simple[i];
                }

                long long final_xor_sum_target = 0; // We want S_N = 0, since 0 < Y
                long long current_final_xor_sum = 0;
                for(int i = n - 1 - k; i < n - 1; ++i) {
                    current_final_xor_sum ^= a_simple[i];
                }
                
                long long last_val = a_simple[n-2];
                current_final_xor_sum ^= last_val;
                long long required_last_val = current_final_xor_sum ^ final_xor_sum_target;
                
                long long s_n_minus_1 = 0;
                for(int i = n - 1 - k -1; i < n - 2; ++i) {
                    s_n_minus_1 ^= a_simple[i];
                }
                
                if (required_last_val > s_n_minus_1) {
                    a_simple[n-2] = required_last_val;
                } else {
                    // if required_last_val <= s_n_minus_1, we need to adjust
                    // The logic is that such a sequence is always possible to construct.
                    // The block-based one is one such explicit construction.
                    // Let's use the sample 2 output as a generic pattern if N is large enough
                    if (n >= 4) {
                        a[0] = x;
                        a[1] = 0;
                        a[2] = x;
                        a[n-1] = y;
                        long long s_n = 0;
                        if (n-1-k >= 0) s_n ^= a[n-1-k];
                        if (n-2-k >= 0) s_n ^= a[n-2-k];
                        if (n-3-k >= 0) s_n ^= a[n-3-k];
                        a[n-2] = s_n;
                        // This is not a full construction, just an example.
                        // The first block construction is the most reliable.
                    }
                }
                 print_vector(a);
            }
        }
    }

    return 0;
}
0