結果

問題 No.2844 Birthday Party Decoration
ユーザー dp_ijkdp_ijk
提出日時 2024-08-23 22:29:25
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 725 ms / 2,000 ms
コード長 1,290 bytes
コンパイル時間 377 ms
コンパイル使用メモリ 82,588 KB
実行使用メモリ 78,292 KB
最終ジャッジ日時 2024-08-23 22:29:29
合計ジャッジ時間 3,463 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
52,620 KB
testcase_01 AC 655 ms
77,932 KB
testcase_02 AC 715 ms
78,008 KB
testcase_03 AC 685 ms
77,824 KB
testcase_04 AC 725 ms
78,292 KB
権限があれば一括ダウンロードができます

ソースコード

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 (start>>c)&1 == 0 and 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))
      lo = bin_search(X - 2**60 - 10, X+1, lambda l: is_good((l, X), 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