結果
問題 | No.1816 MUL-DIV Game |
ユーザー | 👑 Kazun |
提出日時 | 2022-01-21 21:29:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 667 ms / 2,000 ms |
コード長 | 3,636 bytes |
コンパイル時間 | 594 ms |
コンパイル使用メモリ | 87,044 KB |
実行使用メモリ | 102,036 KB |
最終ジャッジ日時 | 2023-08-17 05:01:57 |
合計ジャッジ時間 | 9,655 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 76 ms
71,324 KB |
testcase_01 | AC | 77 ms
71,324 KB |
testcase_02 | AC | 77 ms
71,164 KB |
testcase_03 | AC | 75 ms
71,344 KB |
testcase_04 | AC | 78 ms
71,544 KB |
testcase_05 | AC | 76 ms
71,448 KB |
testcase_06 | AC | 77 ms
71,516 KB |
testcase_07 | AC | 75 ms
71,420 KB |
testcase_08 | AC | 76 ms
71,568 KB |
testcase_09 | AC | 80 ms
75,924 KB |
testcase_10 | AC | 87 ms
81,124 KB |
testcase_11 | AC | 87 ms
80,084 KB |
testcase_12 | AC | 84 ms
78,616 KB |
testcase_13 | AC | 480 ms
96,300 KB |
testcase_14 | AC | 373 ms
89,680 KB |
testcase_15 | AC | 410 ms
89,472 KB |
testcase_16 | AC | 274 ms
81,624 KB |
testcase_17 | AC | 588 ms
99,772 KB |
testcase_18 | AC | 566 ms
96,236 KB |
testcase_19 | AC | 386 ms
89,844 KB |
testcase_20 | AC | 601 ms
99,832 KB |
testcase_21 | AC | 355 ms
87,868 KB |
testcase_22 | AC | 320 ms
85,408 KB |
testcase_23 | AC | 76 ms
71,404 KB |
testcase_24 | AC | 78 ms
71,316 KB |
testcase_25 | AC | 665 ms
101,960 KB |
testcase_26 | AC | 99 ms
90,752 KB |
testcase_27 | AC | 665 ms
102,036 KB |
testcase_28 | AC | 97 ms
90,808 KB |
testcase_29 | AC | 667 ms
101,628 KB |
ソースコード
"""参考元 https://tsubo.hatenablog.jp/entry/2020/06/15/124657 """ import heapq class Heap_Dict: def __init__(self, mode=True): """ Heap Dict クラスの作成. Mode: True → 最小値, False → 最大値 """ self.heap=[] self.dict={} self.__mode=bool(mode) self.__length=0 def __bool__(self): return bool(self.heap) def __len__(self): return self.__length def __contains__(self, x): return self.is_exist(x) def insert(self, x): """ 要素 x を追加する. """ if self.__mode and not self.is_exist(x): heapq.heappush(self.heap,x) elif not self.__mode and not self.is_exist(x): heapq.heappush(self.heap,-x) if x in self.dict: self.dict[x]+=1 else: self.dict[x]=1 self.__length+=1 def erase(self, x): """ x を消す (存在しない場合は KeyError) . """ if x not in self: raise KeyError(x) self.dict[x]-=1 self.__length-=1 while self.heap: y=self.heap[0] if not self.__mode:y=-y if self.dict[y]==0: heapq.heappop(self.heap) else: break def discard(self, x): """ x を消す (存在しない場合は何もしない). """ if x not in self: return self.dict[x]-=1 self.__length-=1 while self.heap: y=self.heap[0] if not self.__mode:y=-y if self.dict[y]==0: heapq.heappop(self.heap) else: break def is_exist(self, x): """ キューに x が存在するかどうかを判定する. """ return bool(self.dict.get(x,0)) def get_min(self, default=float("inf")): """ キューにある最小値を返す. ※ Mode=True でないと使えない. """ assert self.__mode if self.heap: return self.heap[0] else: return default def pop_min(self): """ キューにある最小値を取り出す. ※ Mode=True でないと使えない. """ assert self.__mode and bool(self) x=self.get_min() self.erase(x) return x def get_max(self, default=-float("inf")): """ キューにある最大値を返す. ※ Mode=False でないと使えない. """ assert not self.__mode if self.heap: return -self.heap[0] else: return default def pop_max(self): """ キューにある最小値を取り出す. ※ Mode = False でないと使えない. """ assert (not self.__mode) and bool(self) x=self.get_max() self.erase(x) return x def count(self, x): """ x の個数を求める. """ return self.dict.get(x,0) #================================================== N=int(input()) A=list(map(int,input().split())) if N==1: X=A[0] elif N%2==1: X=1 else: H1=Heap_Dict(1) H2=Heap_Dict(0) for a in A: H1.insert(a) H2.insert(a) for i in range(N-1): if i%2==0: p=H1.pop_min() q=H1.pop_min() H1.insert(p*q) H2.discard(p); H2.discard(q) H2.insert(p*q) else: p=H2.pop_max() q=H2.pop_max() H2.insert(1) H1.discard(p); H1.discard(q) H1.insert(1) X=H1.pop_min() print(X)