結果

問題 No.3223 K-XOR Increasing Sequence
コンテスト
ユーザー Nauclhlt🪷
提出日時 2025-07-05 17:57:45
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 2,247 bytes
コンパイル時間 539 ms
コンパイル使用メモリ 12,160 KB
実行使用メモリ 18,856 KB
最終ジャッジ日時 2025-07-06 17:58:33
合計ジャッジ時間 5,928 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 TLE * 1 -- * 62
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve():
    N, K, X, Y = map(int, input().split())
    
    # 基本ケース
    if N == 1:
        print("Yes")
        print(str(X))
        return
    
    if N <= K:
        A = [X] + [1] * (N - 2) + [Y]
        print("Yes")
        print(' '.join(map(str, A)))
        return
    
    # メイン処理: N > K
    A = [0] * N
    A[0] = X
    A[N-1] = Y
    
    def can_construct():
        # A[1]からA[K-1]まで1で埋める
        for i in range(1, K):
            A[i] = 1
        
        # A[K]からA[N-2]まで条件に従って構築
        for i in range(K, N-1):
            xor_val = 0
            for j in range(i-K, i):
                xor_val ^= A[j]
            
            A[i] = xor_val + 1
            if A[i] >= 2**20:
                return False
        
        # 最終条件: A[N-1] = Yが条件を満たすかチェック
        final_xor = 0
        for j in range(N-1-K, N-1):
            final_xor ^= A[j]
        
        return final_xor < Y
    
    # まず基本戦略を試す
    if can_construct():
        print("Yes")
        print(' '.join(map(str, A)))
        return
    
    # 基本戦略が失敗した場合、調整を試す
    # A[K-1]を変更してみる（K > 1の場合）
    if K > 1:
        for adjust_val in range(2, min(10000, 2**20)):
            A[0] = X
            A[N-1] = Y
            
            # A[1]からA[K-2]まで1、A[K-1]をadjust_valに
            for i in range(1, K-1):
                A[i] = 1
            A[K-1] = adjust_val
            
            # 再構築
            valid = True
            for i in range(K, N-1):
                xor_val = 0
                for j in range(i-K, i):
                    xor_val ^= A[j]
                
                A[i] = xor_val + 1
                if A[i] >= 2**20:
                    valid = False
                    break
            
            if valid:
                # 最終チェック
                final_xor = 0
                for j in range(N-1-K, N-1):
                    final_xor ^= A[j]
                
                if final_xor < Y:
                    print("Yes")
                    print(' '.join(map(str, A)))
                    return
    
    print("No")

solve()
0