結果
問題 |
No.3120 Lower Nim
|
ユーザー |
|
提出日時 | 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 |
ソースコード
#!/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 # 候補なしなら最小1石 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: # 負け局面:最小1石 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()