結果
| 問題 | No.649 ここでちょっとQK！ |
| ユーザー |
👑  SPD_9X2
|
| 提出日時 | 2021-06-18 16:44:29 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 7,813 bytes |
| コンパイル時間 | 1,040 ms |
| コンパイル使用メモリ | 86,908 KB |
| 実行使用メモリ | 759,200 KB |
| 最終ジャッジ日時 | 2023-09-04 13:45:18 |
| 合計ジャッジ時間 | 44,811 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | MLE | - |
| testcase_01 | AC | 74 ms
71,416 KB |
| testcase_02 | AC | 78 ms
71,296 KB |
| testcase_03 | AC | 127 ms
77,412 KB |
| testcase_04 | AC | 865 ms
113,716 KB |
| testcase_05 | AC | 867 ms
114,072 KB |
| testcase_06 | AC | 752 ms
78,308 KB |
| testcase_07 | AC | 76 ms
71,324 KB |
| testcase_08 | AC | 76 ms
71,236 KB |
| testcase_09 | AC | 82 ms
75,852 KB |
| testcase_10 | AC | 80 ms
76,108 KB |
| testcase_11 | AC | 75 ms
71,372 KB |
| testcase_12 | AC | 1,841 ms
388,668 KB |
| testcase_13 | AC | 1,812 ms
389,888 KB |
| testcase_14 | AC | 1,744 ms
365,020 KB |
| testcase_15 | AC | 1,878 ms
397,064 KB |
| testcase_16 | AC | 1,725 ms
425,320 KB |
| testcase_17 | AC | 1,979 ms
450,024 KB |
| testcase_18 | AC | 2,504 ms
486,132 KB |
| testcase_19 | AC | 2,628 ms
511,412 KB |
| testcase_20 | MLE | - |
| testcase_21 | MLE | - |
| testcase_22 | TLE | - |
| testcase_23 | TLE | - |
| testcase_24 | TLE | - |
| testcase_25 | MLE | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
ソースコード
"""
"""
#binaryTrie
#xorパラメータを変更することで、全体にXorを掛けるmultisetとして使える
#depthは、根に近い方が大きいことに注意。根のdepth = bitnumとなる
class BinaryTrie():
class Node():
def __init__(self,depth,parent):
self.depth = depth
self.parent = parent
self.exist = False
self.chnum = 0
self.lchild = None
self.rchild = None
def getparent(self):
return self.parent
def get0child(self,xor):
if (2**(self.depth-1)) & xor == 0:
return self.lchild
else:
return self.rchild
def get1child(self,xor):
if (2**(self.depth-1)) & xor > 0:
return self.lchild
else:
return self.rchild
#if not exist -> create child and return
#if exist -> return
def ret0child(self,xor):
if (2**(self.depth-1)) & xor == 0:
if self.lchild == None:
self.lchild = BinaryTrie.Node(self.depth-1,self)
return self.lchild
else:
if self.rchild == None:
self.rchild = BinaryTrie.Node(self.depth-1,self)
return self.rchild
def ret1child(self,xor):
if (2**(self.depth-1)) & xor > 0:
if self.lchild == None:
self.lchild = BinaryTrie.Node(self.depth-1,self)
return self.lchild
else:
if self.rchild == None:
self.rchild = BinaryTrie.Node(self.depth-1,self)
return self.rchild
def add(self,addnum):
self.chnum += addnum
if self.parent != None:
self.parent.add(addnum)
def eraseable(self):
if self.chnum != 0:
return False
return True
def erase0child(self,xor):
if (2**(self.depth-1)) & xor == 0 and self.lchild != None and self.lchild.eraseable():
self.lchild = None
return True
if (2**(self.depth-1)) & xor > 0 and self.rchild != None and self.rchild.eraseable():
self.rchild = None
return True
return False
def erase1child(self,xor):
if (2**(self.depth-1)) & xor > 0 and self.lchild != None and self.lchild.eraseable():
self.lchild = None
return True
if (2**(self.depth-1)) & xor == 0 and self.rchild != None and self.rchild.eraseable():
self.rchild = None
return True
return False
def __init__(self,bitnum):
self.bitnum = bitnum
self.xor = 0
self.root = self.Node(self.bitnum,None)
def insert(self,x,num): #insert x num times
v = self.root
for i in range(self.bitnum-1,-1,-1):
if 2**i & x == 0:
v = v.ret0child(self.xor)
else:
v = v.ret1child(self.xor)
v.add(num)
while v.parent != None and v.eraseable():
nexv = v.parent
nexv.erase0child(self.xor)
nexv.erase1child(self.xor)
v = nexv
def exist(self,x):
v = self.root
for i in range(self.bitnum-1,-1,-1):
if (2**i) & x == 0:
nexv = v.get0child(self.xor)
if nexv == None:
return False
v = nexv
else:
nexv = v.get1child(self.xor)
if nexv == None:
return False
v = nexv
return True
def count_element(self,x):
v = self.root
for i in range(self.bitnum-1,-1,-1):
if (2**i) & x == 0:
nexv = v.get0child(self.xor)
if nexv == None:
return 0
v = nexv
else:
nexv = v.get1child(self.xor)
if nexv == None:
return 0
v = nexv
return v.chnum
def count_all(self):
return self.root.chnum
def max_element(self):
v = self.root
if self.root.chnum == 0:
return None
ret = 0
for i in range(self.bitnum-1,-1,-1):
ret *= 2
if v.get1child(self.xor) != None:
ret += 1
v = v.get1child(self.xor)
else:
v = v.get0child(self.xor)
return ret
def min_element(self):
v = self.root
if self.root.chnum == 0:
return None
ret = 0
for i in range(self.bitnum-1,-1,-1):
ret *= 2
if v.get0child(self.xor) != None:
v = v.get0child(self.xor)
else:
ret += 1
v = v.get1child(self.xor)
return ret
def kth_element(self,k): #0-indexed
k += 1
if k > self.root.chnum or k < 0:
return None
v = self.root
ret = 0
for i in range(self.bitnum-1,-1,-1):
ret *= 2
ch0 = v.get0child(self.xor)
if ch0 != None and k-ch0.chnum <= 0:
v = ch0
else:
v = v.get1child(self.xor)
ret += 1
if ch0 != None:
k -= ch0.chnum
return ret
def lower_bound(self,x):
return self.upper_bound(x-1)
def upper_bound(self,x):
v = self.root
ret = 0
lasnode = None
lasret = 0
for i in range(self.bitnum-1,-1,-1):
ch0 = v.get0child(self.xor)
ch1 = v.get1child(self.xor)
if 2**i & x == 0:
if ch1 != None:
lasnode = v
lasret = ret
if ch0 != None:
v = ch0
else:
break
else:
if ch1 != None:
ret += 2**i
v = ch1
else:
break
if lasnode == None:
return float("inf")
v = lasnode
ret = lasret
ret += 2**(v.depth-1) #move right
v = lasnode.get1child(self.xor)
while v.depth != 0:
ch0 = v.get0child(self.xor)
ch1 = v.get1child(self.xor)
if ch0 != None:
v = ch0
else:
ret += 2**(v.depth-1)
v = ch1
return ret
def count_less_than(self,x):
v = self.root
ret = 0
for i in range(self.bitnum-1,-1,-1):
ch0 = v.get0child(self.xor)
ch1 = v.get1child(self.xor)
if 2**i & x == 0:
if ch0 != None:
v = ch0
else:
break
else:
if ch0 != None:
ret += ch0.chnum
if ch1 != None:
v = ch1
else:
break
return ret
def count_eqless_than(self,x):
return self.count_less_than(x+1)
def xoring(self,x):
self.xor ^= x
from sys import stdin
BT = BinaryTrie(60)
Q,K = map(int,stdin.readline().split())
for i in range(Q):
query = stdin.readline()[:-1]
if query == "2":
if BT.count_all() >= K:
ans = BT.kth_element(K-1)
print (ans)
BT.insert(ans,-1)
else:
print (-1)
else:
ty,v = map(int,query.split())
BT.insert(v,1)