結果

問題 No.3258 Xor Division Game
ユーザー ゼット
提出日時 2025-09-05 23:09:13
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,288 bytes
コンパイル時間 335 ms
コンパイル使用メモリ 82,780 KB
実行使用メモリ 271,832 KB
最終ジャッジ日時 2025-09-05 23:09:20
合計ジャッジ時間 5,185 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 66
権限があれば一括ダウンロードができます

ソースコード

diff # 

N=int(input())
A=list(map(int,input().split()))
from random import randint
z=randint(1,10**8)
B=set()
for i in range(N):
  B.add(A[i]^z)
B=list(B)
T={}
for i in range(len(B)):
  T[B[i]]=i
for i in range(N):
  A[i]=T[A[i]^z]
from collections import deque
S=deque()
v=[0]*(N+1)
S.append((0,N-1))
result=0
G=[[] for i in range(N+1)]
for i in range(N):
  G[A[i]].append(i)
from bisect import bisect_left,bisect_right
while S:
  l,r=S.pop()
  if l>r:
    continue
  for i in range(l,r+1):
    v[A[i]]+=1
  h=[]
  for i in range(l,r+1):
    if v[A[i]]==1:
      h.append(i)
  while h:
    pos=h.pop()
    if pos<l or pos>r:
      continue
    m0=l-pos
    m1=r-pos
    result+=1
    if m0>=m1:
      S.append((pos+1,r))
      for j in range(pos,r+1):
        v[A[j]]-=1
        if v[A[j]]==1:
          f=bisect_left(G[A[j]],l)
          e=G[A[j]][f]
          if l<=e<pos:
            h.append(e)
      r=pos-1
    else:
      S.append((l,pos-1))
      for j in range(l,pos+1):
        v[A[j]]-=1
        if v[A[j]]==1:
          f=bisect_left(G[A[j]],pos+1)
          if f<len(G[A[j]]):
            e=G[A[j]][f]
            if pos+1<=e<r:
              h.append(e)
      l=pos+1
  for i in range(l,r+1):
    v[A[i]]=0
if result%2==0:
  print('Bob')
else:
  print('Alice')
0