結果

問題 No.3258 Xor Division Game
ユーザー lif4635
提出日時 2025-09-05 18:30:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,010 ms / 2,000 ms
コード長 1,346 bytes
コンパイル時間 208 ms
コンパイル使用メモリ 83,032 KB
実行使用メモリ 229,032 KB
最終ジャッジ日時 2025-09-05 21:17:11
合計ジャッジ時間 37,506 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 67
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict

n = int(input())
f = list(map(int, input().split()))

def division(only, cnt, l, r, idx):
    """
    [l, r) 区間を取り出す
    """
    ncnt = defaultdict(set)
    for i in range(l, r):
        cnt[f[i]].discard(i)
        only.discard(i)
        ncnt[f[i]].add(i)
    
    nonly = set()
    ch = list(ncnt.keys())
    ch.append(f[idx])
    for v in ch:
        if len(ncnt[v]) == 1:
            nonly.add(ncnt[v].pop())
            del ncnt[v]
        if len(cnt[v]) == 1:
            only.add(cnt[v].pop())
            del cnt[v]
    return nonly, ncnt

only = set()
cnt = defaultdict(set)
for i in range(n):
    cnt[f[i]].add(i)
ch = list(cnt.keys())
for v in ch:
    if len(cnt[v]) == 1:
        only.add(cnt[v].pop())
        del cnt[v]

turn = 0
st = [(only, cnt, 0, n)]
while st:
    only, cnt, l, r = st.pop()
    if len(only) == 0: continue
    
    idx = only.pop()
    cnt[f[idx]].discard(idx)
    
    turn += 1
    nl = idx - l
    nr = r - idx - 1
    if nl < nr:
        nonly, ncnt = division(only, cnt, l, idx, idx)
        st.append((nonly, ncnt, l, idx))
        st.append((only, cnt, idx+1, r))
    else:
        nonly, ncnt = division(only, cnt, idx+1, r, idx)
        st.append((only, cnt, l, idx))
        st.append((nonly, ncnt, idx+1, r))

print("Alice" if turn & 1 else "Bob")
0