結果

問題 No.649 ここでちょっとQK！
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2021-06-18 16:44:29
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 7,813 bytes
コンパイル時間 409 ms
コンパイル使用メモリ 82,172 KB
実行使用メモリ 738,996 KB
最終ジャッジ日時 2024-06-22 12:10:44
合計ジャッジ時間 41,924 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 AC 36 ms
54,112 KB
testcase_02 AC 37 ms
54,704 KB
testcase_03 AC 79 ms
75,680 KB
testcase_04 AC 705 ms
111,324 KB
testcase_05 AC 674 ms
111,444 KB
testcase_06 AC 600 ms
76,480 KB
testcase_07 AC 35 ms
54,440 KB
testcase_08 AC 35 ms
55,924 KB
testcase_09 AC 41 ms
61,008 KB
testcase_10 AC 42 ms
61,632 KB
testcase_11 AC 38 ms
54,924 KB
testcase_12 AC 1,760 ms
389,496 KB
testcase_13 AC 1,610 ms
384,108 KB
testcase_14 AC 1,552 ms
359,576 KB
testcase_15 AC 1,682 ms
399,284 KB
testcase_16 AC 1,575 ms
419,616 KB
testcase_17 AC 1,745 ms
451,856 KB
testcase_18 AC 2,133 ms
484,748 KB
testcase_19 AC 2,270 ms
510,832 KB
testcase_20 MLE -
testcase_21 MLE -
testcase_22 MLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 AC 109 ms
75,680 KB
testcase_28 AC 86 ms
76,292 KB
testcase_29 AC 86 ms
76,420 KB
testcase_30 AC 538 ms
90,196 KB
testcase_31 AC 489 ms
91,020 KB
testcase_32 AC 39 ms
56,324 KB
testcase_33 AC 36 ms
55,084 KB
testcase_34 AC 36 ms
53,920 KB
testcase_35 AC 38 ms
54,644 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

"""

#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)
0