結果
| 問題 |
No.649 ここでちょっとQK！
|
| コンテスト | |
| ユーザー |
👑  SPD_9X2
|
| 提出日時 | 2021-06-18 16:42:24 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 7,814 bytes |
| コンパイル時間 | 269 ms |
| コンパイル使用メモリ | 82,404 KB |
| 実行使用メモリ | 684,668 KB |
| 最終ジャッジ日時 | 2024-06-22 12:07:03 |
| 合計ジャッジ時間 | 37,222 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 4 |
| other | AC * 20 TLE * 3 MLE * 3 -- * 6 |
ソースコード
"""
"""
#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(64)
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)