結果

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

ソースコード

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
    
    # XOR特性を利用した解法
    # 戦略：多くの位置で同じ値を使い、XORを0にする
    
    A = [0] * N
    A[0] = X
    A[N-1] = Y
    
    # パターン1: 中間部分を同じ値で埋める（偶数個なら相殺）
    def try_pattern1():
        # A[1]からA[N-2]まで同じ値で埋める
        for val in [1, 2, 3, 4]:  # 小さな値から試す
            for i in range(1, N-1):
                A[i] = val
            
            # 条件チェック
            valid = True
            for i in range(K, N):
                xor_val = 0
                for j in range(i-K, i):
                    xor_val ^= A[j]
                
                if xor_val >= A[i]:
                    valid = False
                    break
            
            if valid:
                return True
        return False
    
    # パターン2: 周期的なパターン
    def try_pattern2():
        # 周期2のパターン [a, b, a, b, ...]
        for a in [1, 2, 3]:
            for b in [1, 2, 3]:
                if a == b:
                    continue
                
                for i in range(1, N-1):
                    A[i] = a if i % 2 == 1 else b
                
                # 条件チェック
                valid = True
                for i in range(K, N):
                    xor_val = 0
                    for j in range(i-K, i):
                        xor_val ^= A[j]
                    
                    if xor_val >= A[i]:
                        valid = False
                        break
                
                if valid:
                    return True
        return False
    
    # パターン3: XORが0になる構造を作る
    def try_pattern3():
        # K個の組み合わせでXORが0になるパターン
        if K % 2 == 0:  # Kが偶数なら、同じ値をK/2個ずつ
            val = 1
            for i in range(1, N-1):
                A[i] = val
            
            # 条件チェック
            valid = True
            for i in range(K, N):
                xor_val = 0
                for j in range(i-K, i):
                    xor_val ^= A[j]
                
                if xor_val >= A[i]:
                    valid = False
                    break
            
            if valid:
                return True
        return False
    
    # 各パターンを試す
    if try_pattern1():
        print("Yes")
        print(' '.join(map(str, A)))
        return
    
    if try_pattern2():
        print("Yes")
        print(' '.join(map(str, A)))
        return
    
    if try_pattern3():
        print("Yes")
        print(' '.join(map(str, A)))
        return
    
    print("No")

solve()
0