結果

問題 No.3120 Lower Nim
コンテスト
ユーザー keigo kuwata
提出日時 2025-04-24 14:43:28
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 3,471 bytes
コンパイル時間 331 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 28,576 KB
平均クエリ数 2212.45
最終ジャッジ日時 2025-04-24 14:43:39
合計ジャッジ時間 10,214 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 37 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env python3
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int, input().split()))
    # 初期 XOR とビット集合構築
    total_xor = 0
    MAX_BITS = max(A).bit_length() if A else 0
    bit_groups = [set() for _ in range(MAX_BITS)]
    for i, a in enumerate(A):
        total_xor ^= a
        for b in range(a.bit_length()):
            if (a >> b) & 1:
                bit_groups[b].add(i)

    # 最小非ゼロ山ポインタ
    next_nonzero = 0

    # 先手・後手決定
    if total_xor != 0:
        print("First")
        our_turn = True
    else:
        print("Second")
        our_turn = False
    sys.stdout.flush()

    K = 10**9  # 初期制限は十分大きく

    while True:
        if not our_turn:
            # ─── ジャッジの手 ───
            line = input().split()
            if not line:
                return
            i, x = map(int, line)
            ret = int(input())
            if ret == -1:
                return  # 敗北
            idx = i - 1
            old = A[idx]
            new = old - x
            # XOR 差分更新
            total_xor ^= old ^ new
            # ビット集合更新
            diff = old ^ new
            for b in range(diff.bit_length()):
                if (diff >> b) & 1:
                    if (new >> b) & 1:
                        bit_groups[b].add(idx)
                    else:
                        bit_groups[b].discard(idx)
            A[idx] = new
            K = x
            our_turn = True

        else:
            # ─── 自分の手 ───
            if total_xor != 0:
                b = total_xor.bit_length() - 1
                move_idx = move_x = None
                # bit_groups[b] から最初の候補を試す
                for idx in bit_groups[b]:
                    old = A[idx]
                    if old == 0: 
                        continue
                    target = old ^ total_xor
                    x = old - target
                    if 1 <= x <= K:
                        move_idx, move_x = idx, x
                        break
                # 候補なしなら最小１石
                if move_x is None:
                    while next_nonzero < N and A[next_nonzero] == 0:
                        next_nonzero += 1
                    move_idx = next_nonzero
                    move_x = min(A[move_idx], K)
            else:
                # 負け局面：最小１石
                while next_nonzero < N and A[next_nonzero] == 0:
                    next_nonzero += 1
                move_idx = next_nonzero
                move_x = min(A[move_idx], K)

            # 手を出力
            print(move_idx+1, move_x)
            sys.stdout.flush()

            # 自分の手による状態更新
            old = A[move_idx]
            new = old - move_x
            total_xor ^= old ^ new
            diff = old ^ new
            for b in range(diff.bit_length()):
                if (diff >> b) & 1:
                    if (new >> b) & 1:
                        bit_groups[b].add(move_idx)
                    else:
                        bit_groups[b].discard(move_idx)
            A[move_idx] = new
            K = move_x

            # Judge から ret を読む
            ret = int(input())
            if ret == 1 or ret == -1:
                return
            our_turn = False

if __name__ == "__main__":
    main()
0