結果

問題 No.2977 Kth Xor Pair
ユーザー titia
提出日時 2024-12-15 04:50:21
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,091 bytes
コンパイル時間 969 ms
コンパイル使用メモリ 81,968 KB
実行使用メモリ 649,552 KB
最終ジャッジ日時 2024-12-15 04:52:04
合計ジャッジ時間 98,778 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 14 WA * 1 TLE * 18 MLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

N,K=map(int,input().split())
A=list(map(int,input().split()))

r=N*(N-1)//2-K+1

# Trie木

Next_node_id0=[-1]
Next_node_id1=[-1]
Parent_id=[-1] # 親ノード
Depth=[0] # Trieのノードの深さ
Count=[0] # Trieのノードの重複度

LAST=[]

Nodes_id=1 # 以下、標準入力で与えられたN個の文字列を追加する実装
for i in range(N):
    a=A[i]
    NOW=0
    for i in range(30,-1,-1):
        if a & (1<<i) == 0:
            NEXT=0
        else:
            NEXT=1

        if NEXT==0:
        
            if Next_node_id0[NOW]==-1: # Nodeを追加する場合
                Next_node_id0[NOW]=Nodes_id

                Next_node_id0.append(-1)
                Next_node_id1.append(-1)
                Parent_id.append(NOW)
                Depth.append(Depth[NOW]+1)
                Count.append(0)

                NOW=Nodes_id         
                Nodes_id+=1

            else: # 追加しない場合
                NOW=Next_node_id0[NOW]
        else:
            if Next_node_id1[NOW]==-1: # Nodeを追加する場合
                Next_node_id1[NOW]=Nodes_id

                Next_node_id0.append(-1)
                Next_node_id1.append(-1)
                Parent_id.append(NOW)
                Depth.append(Depth[NOW]+1)
                Count.append(0)

                NOW=Nodes_id         
                Nodes_id+=1

            else: # 追加しない場合
                NOW=Next_node_id1[NOW]

    Count[NOW]+=1 # 終端に印を付ける
    LAST.append(NOW)

Count2=[0]*len(Count)

for x in LAST:
    while x!=-1:
        Count2[x]+=1
        x=Parent_id[x]

OK=0
NG=max(A)+1

# OK以上のものがr個あればOK

while NG>OK+1:
    mid=(OK+NG)//2
    count=0

    for a in A:
        now=0
        count2=0
        flag=0
        for dep in range(30,-1,-1):
            
            x,y=Next_node_id0[now],Next_node_id1[now]

            #print(now,x,y,Count2[x],Count2[y],count2)
            
            if ((1<<dep) & a == 0) and ((1<<dep) & mid == 0):
                if y!=-1:
                    count2+=Count2[y]

                if x!=-1:
                    now=x
                else:
                    flag=1
                    break

            elif ((1<<dep) & a == 0) and ((1<<dep) & mid != 0):
                if y!=-1:
                    now=y
                else:
                    flag=1
                    break
            elif ((1<<dep) & a != 0) and ((1<<dep) & mid == 0):
                if x!=-1:
                    count2+=Count2[x]

                if y!=-1:
                    now=y
                else:
                    flag=1
                    break
            else:
                if x!=-1:
                    now=x
                else:
                    flag=1
                    break

        #print(count2,now,flag)

        if flag==0:
            count2+=Count2[now]

        #print(a,"^x",">=",mid,"を満たすxをcount",count2)
        count+=count2

    #print(count)

    if count//2>=r:
        OK=mid
    else:
        NG=mid

print(OK)
0