from sortedcontainers import SortedList
from typing import List
from collections import defaultdict, deque
from itertools import accumulate
import heapq
import sys
'''
1 设n为结果 max_n/2 <= n <= max
2 m为去头 结果为 max_n/2 | m
3 最大 - 其它的| 必在 m 里
4 <
4 dp[0][n]=s d
'''
class Solution:
def log(self, *s):
pass
def ringGame(self, challenge: List[int]) -> int:
n=len(challenge)
max_value=challenge[0]
max_index=0
for i in range(1,len(challenge)):
if challenge[i]>max_value:
max_value=challenge[i]
max_index=i
challenge = challenge[max_index:]+challenge+challenge[:max_index+1]
n3=len(challenge)
def check(m) :
i = 1
while i < n3:
# 尝试以关卡i为起点
if challenge[i] > m :
i += 1
continue
s, l, r = m|score_left[i]|score_right[i], idx_left[i], idx_right[i]
while True :
if r-l > n :
return True # 已挑战完所以关卡
# 向两边挑战关卡，并更新积分
if challenge[l] <= s :
s |= score_left[l]
l = idx_left[l]
if challenge[r] <= s :
s |= score_right[r]
r = idx_right[r]
else : break
i = r # 扩展经过的点都可以不必再尝试作为起点；
return False
# 预计算出以某个关卡为起点（也以它的挑战分为初始分），单纯向左或向右能扩展多远和扩展后的积分
score_left, idx_left = challenge[:], [0]*n3
for i in range(n3) :
j = i-1
while j >= 0 and challenge[j] <= score_left[i] :
score_left[i] |= score_left[j]
j = idx_left[j]
idx_left[i] = j
score_right, idx_right = challenge[:], [0]*n3
for i in range(n3-1, -1, -1) :
j = i+1
while j < n3 and challenge[j] <= score_left[i] :
score_right[i] |= score_right[j]
j = idx_right[j]
idx_right[i] = j
# self.log(challenge)
# self.log(score_right)
# self.log(idx_right)
# 从高到低确定答案的二进制位
bit = 1 << (max_value.bit_length()-1)
res = bit
while bit:
bit >>= 1
if not check(res | (bit-1)) :
res |= bit
return res
def baoli(self,challenge):
def util(ret,i):
visited=[False]*len(challenge)
stacks=[]
heapq.heappush(stacks,[challenge[i],i])
while len(stacks):
next_v,next_i=heapq.heappop(stacks)
if next_v>ret:
return False
visited[next_i]=True
ret = ret|next_v
next_i_right=(next_i+1)%len(challenge)
next_i_left=(next_i-1+len(challenge))%len(challenge)
if not visited[next_i_right]:
heapq.heappush(stacks,[challenge[next_i_right],next_i_right])
if not visited[next_i_left]:
heapq.heappush(stacks,[challenge[next_i_left],next_i_left])
return True
def check(ret):
for i in range(len(challenge)):
if challenge[i]<=ret and util(ret,i):
return True
return False
while ret<max_score:
mid=(ret+max_score)//2
self.log(ret,mid,max_score)
if check(mid):
max_score=mid
else:
ret=mid+1
return max_score
def run(self, *args):
return self.ringGame(*args)
class SolutionDebug(Solution):
logs = ""
def log(self, *s):
self.logs += " ".join([str(v) for v in s])+"
"
def run(self, *args, **kw) -> int:
self.logs = ""
return super().run(*args, **kw)
if __name__ == '__main__':
s = SolutionDebug()
null=None
true=True
false=False
for case in [
[[1,180,447],266],
[[5,4,6,2,7],4],
[[12,7,11,3,9],8],
[[7,7],7],
[[1,17,1,19,1],18],
[[1,1,1],1]
]:
s.logs = ""
e = s.run(*case[:-1])
if e != case[-1]:
print(e, case)
print(s.logs)
break
from sortedcontainers import SortedList
from typing import List
from collections import defaultdict, deque
from itertools import accumulate
import heapq
import sys
class Solution:
def log(self, *s):
pass # 日志函数，用于调试
def ringGame(self, challenge: List[int]) -> int:
n = len(challenge)
max_value = max(challenge)
max_index = challenge.index(max_value)
# 重构数组使其线性化，简化问题
challenge = challenge[max_index:] + challenge[:max_index]
n3 = len(challenge)
def check(m):
# 检查起始积分m是否足够挑战所有关卡
for i in range(1, n3):
if challenge[i] > m:
continue
s, l, r = m | challenge[i], i - 1, i + 1
while True:
if r - l > n:
return True
if l >= 0 and challenge[l] <= s:
s |= challenge[l]
l -= 1
if r < n3 and challenge[r] <= s:
s |= challenge[r]
r += 1
else:
break
return False
# 二进制搜索最低有效积分
res = 1 << max_value.bit_length() - 1
while res:
if not check(res):
res <<= 1
else:
res >>= 1
return res
def run(self, *args):
return self.ringGame(*args)
if __name__ == '__main__':
s = Solution()
result = s.run([5,4,6,2,7])
print(result) # 应该输出4