結果

問題 No.2844 Birthday Party Decoration
ユーザー dp_ijkdp_ijk
提出日時 2024-08-23 21:47:36
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,320 bytes
コンパイル時間 203 ms
コンパイル使用メモリ 82,576 KB
実行使用メモリ 78,488 KB
最終ジャッジ日時 2024-08-23 21:47:39
合計ジャッジ時間 3,286 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
52,888 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

def bin_search(ok, ng, is_ok):
   while abs(ok-ng) > 1:
      mid = (ok+ng)//2
      if is_ok(mid):
         ok = mid
      else:
         ng = mid
   return ok
def solve(N, X, C):
   INF = float("INF")
   def is_good(range_, C):
      start, stop = range_
      for c in C:
         m = start + ((1<<c) - start) % (1<<(c+1))
         if stop <= m:
            return False
      return True
   S = set(C)
   pos = X
   tovisit = []
   while True:
      found = []
      for c in S:
         if pos&(1<<c):
            found.append(c)
      if found:
         for c in found:
            S.remove(c)
         tovisit.append((pos, found[:]))
      if not S:
         break
      cands = []
      for c in S:
         npos = pos + ((1<<c) - pos) % (1<<(c+1))
         cands.append(npos)
      pos = min(cands)
   tovisit.insert(0, (X, []))
   used = []
   cands = []
   for pos, found in tovisit:
      used += found
      D = list(set(C) - set(used))
      if not D:
         lo = X
      else:
         lo = bin_search(X - 2**60 - 10, X+1, lambda l: is_good((l, X+1), D))
         if lo < 0: lo = -INF
      cands.append((pos - lo) * 2)
   ans = min(cands)
   return ans
T = int(input())
for _ in range(T):
   N, X = map(int, input().split())
   C = list(map(int, input().split()))
   ans = solve(N, X, C)
   print(ans)
0